【bzoj4025】【二分图】【lct】-白红宇的个人博客

【bzoj4025】【二分图】【lct】

发布日期：2021-11-16 15:38:20 浏览次数：6 分类：技术文章

本文共 2638 字，大约阅读时间需要 8 分钟。

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。

题解：

每条边的权值设为它消失的时间。

lct维护最大生成树。lct中维护树边,另开一个集合维护非树边。

从小到达枚举时间进行加边和删边。

对于加边,判断加边是否会形成奇环,并且更新最大生成树和集合.

对于删边，如果是最大生成树里的边就在lct中删掉。否则仅在集合中删掉即可。

代码：

#include
     
      #include
      
       #include
       
        #define N 400010using namespace std;int point1[N],point2[N],n,m,T,cnt,size[N],s[N],c[N][2],fa[N],mn[N],v[N];int in[N],on[N],next[N],rev[N],num,ss,tt;struct use{int st,en,w;}e[N];struct use2{int st,en;}b[N];inline int read(){	int x=0,f=1;char ch=getchar();	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}	return x*f;}void add1(int x,int y){next[++cnt]=point1[x];point1[x]=cnt;b[cnt].en=y;}void add2(int x,int y){next[++cnt]=point2[x];point2[x]=cnt;b[cnt].en=y;}bool isroot(int x){return c[fa[x]][1]!=x&&c[fa[x]][0]!=x;}void updata(int x){  int l=c[x][0],r=c[x][1];  size[x]=size[l]+size[r]+(x>n);mn[x]=x;  if (v[mn[x]]>v[mn[l]]) mn[x]=mn[l];  if (v[mn[x]]>v[mn[r]]) mn[x]=mn[r];}void pushdown(int x){  int l=c[x][0],r=c[x][1];  if (rev[x]){rev[l]^=1;rev[r]^=1;rev[x]^=1;swap(c[x][0],c[x][1]);}}void rotata(int x){  int l,r,y=fa[x],z=fa[y];  if (c[y][0]==x) l=0;else l=1;r=l^1;  if (!isroot(y)){if (c[z][0]==y) c[z][0]=x;else c[z][1]=x;}  fa[x]=z;fa[c[x][r]]=y;fa[y]=x;  c[y][l]=c[x][r];c[x][r]=y;  updata(y);updata(x);}void splay(int x){  int top(0);s[++top]=x;  for (int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];  for (int i=top;i;i--)pushdown(s[i]);  while (!isroot(x)){    int y=fa[x],z=fa[y];    if (!isroot(y)){if (c[y][0]==x^c[z][0]==y) rotata(y);else rotata(x);}    rotata(x);  }}void access(int x){int t(0);while (x){splay(x);c[x][1]=t;t=x;updata(x);x=fa[x];}}void makeroot(int x){access(x);splay(x);rev[x]^=1;} void split(int x,int y){makeroot(y);access(x);splay(x);}void link(int x,int y){makeroot(x);fa[x]=y;}void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;}int find(int x){access(x);splay(x);int y=x;while (c[y][0]) y=c[y][0];return y;}void ins(int x){ int u=e[x].st,v=e[x].en; if (u==v){in[x]=1;num++;return;} if(find(u)!=find(v)){on[x]=1;link(u,x+n);link(v,x+n);} else{   split(u,v);int y=mn[u]-n;   if (e[y].w

转载地址：https://blog.csdn.net/sunshinezff/article/details/50983232 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj2816】【ZJOI2012】【网络】【lct】

下一篇：【bzoj2594】【WC2006】【水管局长加强版】【lct】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！