bzoj 4025 二分图 lct

题目传送门

题解：

首先关于二分图的性质，就是没有奇环边。题目其实就是让你判断每个时段之内有没有奇环。

其次 lct 只能维护树，(反正对于我这种菜鸟选手只会维护树)，那么对于一棵树来说，填上一条边会形成奇数环，或者偶数环。

现在我们考虑偶数环，对于偶数环来说，如果加上一条边都能使得这个图出现一个奇数环，我们现在任意删除一条边，都还是会存在一个奇数环。

那么当出现偶数环的情况下，我们可以删除一条边，保存树的性质。

当出现奇数环的时候，我们也需要删除某一条边，并且需要标记被树上删除的那个边是什么边，直到那个边消失之前，这个图就存在奇数环。

我们现在按照边的消失的时间从小到大删除边。因为找替换边太麻烦了，不好处理。我们按照消失的时间处理之后，就一定不会存在替换的边。

删除的时候，也要顺带删除掉标记。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("2.in","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define lch(x) tr[x].son[0]

 #define rch(x) tr[x].son[1]

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 5e5 + ;

 struct Node{

     int rev, rt, sz;

     int son[], pre;

     int t, tt,  id;

     void init(){

         sz = rt = ; rev = pre = son[] = son[] = ;

         tt = t = inf;

     }

 }tr[N];

 void Push_Rev(int x){

     if(!x) return ;

     swap(lch(x), rch(x));

     tr[x].rev ^= ;

 }

 void Push_Up(int x){

     if(!x) return ;

     tr[x].sz = tr[lch(x)].sz + tr[rch(x)].sz + ;

     tr[x].id = x;

     tr[x].tt = tr[x].t;

     if(tr[x].tt > tr[lch(x)].tt) tr[x].id = tr[lch(x)].id, tr[x].tt = tr[lch(x)].tt;

     if(tr[x].tt > tr[rch(x)].tt) tr[x].id = tr[rch(x)].id, tr[x].tt = tr[rch(x)].tt;

 }

 void Push_Down(int x){

    if(tr[x].rev){

         tr[x].rev = ;

         Push_Rev(lch(x));

         Push_Rev(rch(x));

     }

 }

 void Rev(int x){

     if(!tr[x].rt) Rev(tr[x].pre);

     Push_Down(x);

 }

 void rotate(int x){

     if(tr[x].rt) return;

     int y = tr[x].pre, z = tr[y].pre;

     int k = (rch(y) == x);

     tr[y].son[k] = tr[x].son[k^];

     tr[tr[y].son[k]].pre = y;

     tr[x].son[k^] = y;

     tr[y].pre = x;

     tr[x].pre = z;

     if(tr[y].rt) tr[y].rt = , tr[x].rt = ;

     else tr[z].son[rch(z) == y] = x;

     Push_Up(y);

 }

 void Splay(int x){

      Rev(x);

      while(!tr[x].rt){

         int y = tr[x].pre, z = tr[y].pre;

         if(!tr[y].rt){

             if(( x == rch(y) ) != (y == rch(z))) rotate(y);

             else rotate(x);

         }

         rotate(x);

     }

     Push_Up(x);

 }

 void Access(int x){

     int y = ;

     do{

         Splay(x);

         tr[rch(x)].rt = ;

         rch(x) = y;

         tr[y].rt = ;

         Push_Up(x);

         y = x;

         x = tr[x].pre;

     }while(x);

 }

 void Make_rt(int x){

     Access(x);

     Splay(x);

     Push_Rev(x);

 }

 void link(int u, int v){

     Make_rt(u);

     tr[u].pre = v;

 }

 void cut(int u, int v){

     Make_rt(u);

     Access(v);

     Splay(v);

     tr[lch(v)].pre = ;

     tr[lch(v)].rt = ;

     tr[v].pre = ;

     lch(v) = ;

 }

 bool judge(int u, int v){

     while(tr[u].pre) u = tr[u].pre;

     while(tr[v].pre) v = tr[v].pre;

     return u == v;

 }

 int n, m, u, v, st, ed, T, id, odd, t;

 int tot;

 int vis[N], in[N];

 struct node{

     int u, v, id, t, t2;

     bool operator < (const node & x) const {

         if(t != x.t) return t < x.t;

         return t2 < x.t2;

     }

 }A[N];

 void add(int u, int v, int id, int t, int t2){

     ++tot;

     A[tot].u = u; A[tot].v = v; A[tot].id = id;

     A[tot].t = t; A[tot].t2 = t2;

 }

 int main(){

     tr[].tt = tr[].t = inf;

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

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

         tr[i].init();

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

         scanf("%d%d%d%d", &u, &v, &st, &ed);

         tr[i+n].t = ed;

         if(st == ed) continue;

         add(u, v, n+i, st, ed);

         add(u, v, n+i, ed, -);

     }

     sort(A+, A++tot);

     int j = ;

     for(int i = ; i < T; i++){

         while(j <= tot && A[j].t == i){

             u = A[j].u, v = A[j].v, id = A[j].id, t = A[j].t2;

             if(t == -){

                 if(in[id]){

                     cut(u, id);

                     cut(v, id);

                 }

                 odd -= vis[id];

             }

             else {

                 if(u == v) {

                     vis[id] = ;

                     odd++;

                 }

                 else {

                     if(!judge(u, v)){

                         link(u, id);

                         link(v, id);

                         in[id] = ;

                     }

                     else {

                         Make_rt(u);

                         Access(v);

                         Splay(v);

                         int sz = tr[v].sz / ;

                         int p = tr[v].id;

                         int tt = tr[v].tt;

                         if(tt >= t){

                             if(sz% == ){

                                 odd++;

                                 vis[id] = ;

                             }

                         }

                         else {

                             if(sz% == ){

                                 odd++;

                                 vis[p] = ;

                             }

                             cut(u, p);

                             cut(v, p);

                             in[p] = ;

                             link(u, id);

                             link(v, id);

                             in[id] = ;

                         }

                     }

                 }

             }

             j++;

         }

         if(odd) puts("No");

         else puts("Yes");

     }

     return ;

 }

巴特西

bzoj 4025 二分图 lct

最新文章

热门文章