bzoj 4025 二分圖
【題目大意】
有n個點m條邊,邊會在start時刻出現在end時刻消失,求對于每一段時間,該圖是不是一個二分圖。
判斷二分圖的一個簡單的方法:是否存在奇環
若存在奇環,就不是二分圖。
假設加入一條u->v的邊,u,v已經聯通,怎麼知道是否是一個奇環呢?隻需要知道u,v之間的距離就行了。距離為偶數則是一個奇環。
路徑?加邊?删邊?
很容易就想到是LCT。
維護u->v的距離。
每次加入一條邊,就判斷是否先前已經聯通,否,則家父,若是,就判斷u,v之間的距離。
假若已經構成一個奇環,那麼,在這個環的任意一條邊都未被删除前,都不是二分圖。
那就在維護一個minv,表示最小的end值。加入一條邊構成了環,就删掉最小end值的那條邊,加入新邊。
由于是最小值,删掉不會有影響。(最小的end值的那條邊肯定是先消失的)
要把邊拆成點,為了記錄min值,以及對應的邊。
細節,慢慢處理就好了。(被坑了好久……)
注意:有自環,需特判。
【附上代碼】
#include<cstdio>
#include<algorithm>
#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))
using namespace std;
const int N=;
int n,m,T,cnt,len;
struct tree
{
tree *c[],*f,*pp,*L,*R;
bool flip;
int minv,val,siz;
int d() { return (f->c[]==this); }
void sc(tree *x,int d) { (c[d]=x)->f=this; }
} nil[N*],*ro[N*],*stack[N*];
struct data { int u,v,start,end; } d[N<<1];
int ans[N];
tree *newtree()
{
nil[++cnt]=nil[];
return nil+cnt;
}
void down(tree *x)
{
if(x==nil) return;
if(x->flip)
{
x->flip=;
swap(x->c[],x->c[]);
if(x->c[]!=nil) x->c[]->flip^=;
if(x->c[]!=nil) x->c[]->flip^=;
}
}
void up(tree *x)
{
if(x==nil) return;
x->minv=x->val; x->siz=;
if(x->c[]!=nil) x->minv=imin(x->minv,x->c[]->minv),x->siz+=x->c[]->siz;
if(x->c[]!=nil) x->minv=imin(x->minv,x->c[]->minv),x->siz+=x->c[]->siz;
}
void rotate(tree *x)
{
int d=x->d();
tree *y=x->f;
y->sc(x->c[!d],d);
if(y->f==nil) x->f=nil; else y->f->sc(x,y->d());
x->sc(y,!d);
up(y); up(x);
x->pp=y->pp;
y->pp=nil;
}
void splay(tree *x)
{
int hy=;
stack[hy]=x;
for(;stack[hy]->f!=nil;hy++) stack[hy+]=stack[hy]->f;
for(;hy;) down(stack[hy]),hy--;
for(tree *y;x->f!=nil;)
{
y=x->f;
if(y->f!=nil)
(x->d()^y->d())?rotate(x):rotate(y);
rotate(x);
}
}
void access(tree *x)
{
tree *y=nil;
while(x!=nil)
{
splay(x);
if(x->c[]!=nil)
{
x->c[]->f=nil;
x->c[]->pp=x;
}
x->c[]=y;
if(y!=nil)
{
y->f=x;
y->pp=nil;
}
up(x);
y=x; x=x->pp;
}
}
void evert(tree *x)
{
access(x);
splay(x);
x->flip^=;
}
void link(tree *x,tree *y)
{
evert(y);
y->pp=x;
}
void cut(tree *x,tree *y)
{
evert(x);
access(y);
splay(y);
if(y->c[]!=nil)
{
y->c[]->f=nil;
y->c[]=nil;
}
up(y);
}
tree *findroot(tree *x)
{
access(x);
splay(x);
while(x->c[]!=nil)
{
x=x->c[];
down(x);
}
splay(x);
return x;
}
tree *findmin(tree *x,tree *y)
{
evert(x);
access(y);
splay(x); down(x);
len=(x->siz+)>>;
int find=x->minv;
for(;;)
{
if(x->val==find) break;
if(x->c[]!=nil && x->c[]->minv==find) x=x->c[];
else x=x->c[];
down(x);
}
splay(x);
return x;
}
bool cmp(data A,data B) { return (A.start<B.start); }
int main()
{
scanf("%d%d%d",&n,&m,&T); cnt=;
nil->val=nil->minv=; nil->siz=; nil->pp=nil;
nil->f=nil->c[]=nil->c[]=nil->L=nil->R=nil;
for(int i=;i<=m;i++) scanf("%d%d%d%d",&d[i].u,&d[i].v,&d[i].start,&d[i].end);
sort(d+,d++m,cmp);
for(int i=;i<=n;i++) ro[i]=newtree();
for(int i=;i<=m;i++)
{
ro[n+i]=newtree();
ro[n+i]->val=d[i].end; ro[n+i]->minv=d[i].end;
ro[n+i]->L=ro[d[i].u]; ro[n+i]->R=ro[d[i].v];
}
for(int i=;i<=m;i++)
{
if(d[i].u==d[i].v)
{
ans[d[i].start]++; ans[d[i].end]--;
continue;
}
if(findroot(ro[d[i].u])!=findroot(ro[d[i].v]))
{
link(ro[d[i].u],ro[n+i]);
link(ro[n+i],ro[d[i].v]);
}
else
{
tree *getmin=findmin(ro[d[i].u],ro[d[i].v]);
if(d[i].start<getmin->val && (len&))
{
ans[d[i].start]++;
ans[imin(getmin->val,d[i].end)]--; //重點啊,我就被這裡坑了
}
if(d[i].end>getmin->val)
{
cut(getmin,getmin->L);
cut(getmin,getmin->R);
link(ro[d[i].u],ro[n+i]);
link(ro[n+i],ro[d[i].v]);
}
}
}
int yu=;
for(int i=;i<T;i++)
{
yu+=ans[i];
if(yu>) printf("No\n"); else printf("Yes\n");
}
return ;
}
【其他思路】
分治+可回溯并查集(就是不帶路徑壓縮的并查集)
Solve(L,R,S)表示處理L到R這個時間段,有關聯的邊集為S。
如果存在L->R的時間段的邊,且加入後構成了奇環,那麼L->R這段時間都不為二分圖,直接退出。
把邊集劃分為左右兩邊,即邊與左區間的交集歸左邊,右邊的交集歸右邊。(是start和end的交集)
然後先處理左邊,再處理右邊就行了。
具體的看這裡,我沒寫cdq分治,這是我同學的