【BZOJ 4025】（CDQ？还是整体二分？+并查集及它的恢复操作）

4025: 二分图

Description

神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。

Input

输入数据的第一行是三个整数n,m,T。

第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这条边在start时刻出现，在第end时刻消失。

Output

输出包含T行。在第i行中，如果第i时间段内这个图是二分图，那么输出“Yes”，否则输出“No”，不含引号。

Sample Input

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2

Sample Output

Yes
No
Yes

HINT

样例说明：

0时刻，出现两条边1-2和2-3。

第1时间段内，这个图是二分图，输出Yes。

1时刻，出现一条边1-3。

第2时间段内，这个图不是二分图，输出No。

2时刻，1-2和1-3两条边消失。

第3时间段内，只有一条边2-3，这个图是二分图，输出Yes。

数据范围：

n<=100000，m<=200000，T<=100000，1<=u,v<=n，0<=start<=end<=T。

Source

【分析】

　　%%%大颓果，你可以看她的按秩合并题解：http://blog.csdn.net/u010336344/article/details/55194864

　　我打的是最简单那种并查集，每次修改father和dis的时候把操作压入栈里面，回溯的时候恢复并查集。

　　【表示第一次恢复并查集，从来没想过这个。。不过并查集时间很快的话应该也不会很耗空间吧？

　　我觉得主方法更像整体二分，T给的是一个区间，像线段树一样当完全在[l,r]中的时候进行操作，其余操作分到左右两个区间里面做。

　　回溯的时候恢复并查集。

　　大概就是这样。

　　哦对了，二分图就是看看是否有奇环，有的话一定不是二分图。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<stack>

 using namespace std;

 #define Maxn 100010

 struct node {int x,y,s,t;};

 vector<node > S;

 int fa[Maxn],dis[Maxn];

 bool ans[Maxn];

 struct nnode {int x,f,d;};

 stack<nnode> sta;

 void mak_f(int x,int ff,int dd)

 {

     nnode tt;

     tt.x=x;tt.f=fa[x];tt.d=dis[x];

     sta.push(tt);

     fa[x]=ff;

     dis[x]=dd;

 }

 int ffa(int x)

 {

     if(fa[x]!=x)

     {

         int ff=ffa(fa[x]);

         mak_f(x,ff,(dis[fa[x]]+dis[x])%);//fa[x]=ffa(fa[x]);

     }

     return fa[x];

 }

 void ffind(int l,int r,vector<node> M)

 {

     vector<node> ll,rr;

     ll.clear();rr.clear();

     int mid=(l+r)>>,now=sta.size();

     bool ok=;

     for(int i=;i<M.size();i++)

     {

         node t=M[i];

         if(t.s==l&&t.t==r)

         {

             if(ffa(t.x)==ffa(t.y))

             {

                 if(dis[t.x]==dis[t.y]) {ok=;break;}

             }

             else

             {

                 if(ffa(t.x)!=t.x)

                 {

                     mak_f(ffa(t.x),t.x,dis[t.x]);

                     mak_f(t.x,t.x,);

                 }

                 mak_f(t.x,t.y,);

             }

         }

         else if(t.t<=mid) ll.push_back(t);

         else if(t.s>mid) rr.push_back(t);

         else

         {

             node tt=t;tt.t=mid;

             ll.push_back(tt);tt.s=mid+;tt.t=t.t;

             rr.push_back(tt);

         }

     }

     if(l!=r&&!ok)

     {

         ffind(l,mid,ll);ffind(mid+,r,rr);

     }

     while(sta.size()>now)

     {

         nnode nw=sta.top();

         sta.pop();

         fa[nw.x]=nw.f;dis[nw.x]=nw.d;

     }

     if(ok)

     {

         for(int i=l;i<=r;i++) ans[i]=;

     }

 }

 int main()

 {

     int n,m,T;

     scanf("%d%d%d",&n,&m,&T);

     S.clear();

     for(int i=;i<=n;i++) fa[i]=i;

     for(int i=;i<=n;i++) dis[i]=;

     for(int i=;i<=m;i++)

     {

         node t;

         scanf("%d%d%d%d",&t.x,&t.y,&t.s,&t.t);

         t.s++;

         if(t.s<=t.t) S.push_back(t);

     }

     for(int i=;i<=T;i++) ans[i]=;

     ffind(,T,S);

     for(int i=;i<=T;i++) if(ans[i]) printf("Yes\n");

     else printf("No\n");

     return ;

 }

2017-02-16 22:07:48

巴特西

【BZOJ 4025】（CDQ？还是整体二分？+并查集及它的恢复操作）

4025: 二分图

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

【BZOJ 4025】 （CDQ？还是整体二分？+并查集及它的恢复操作）

4025: 二分图

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

【BZOJ 4025】（CDQ？还是整体二分？+并查集及它的恢复操作）