P10777 BZOJ3706 反色刷

· · 题解

首先先进行存在性判定，由于要走奇数次黑边，偶数次白边，所以只有黑边会改变节点度数的奇偶性，所以不妨先只连黑边，如果出现度数为奇数的节点，那么一定无解。因为题目要求只能从一个点出发并且最终返回这个节点，那么遍历过程中每个点的进边和出边数量一定相同，也就一定不会改变其度数的奇偶性，所以度数为奇数的点最后度数一定无法变为零，一定无解。

然后考虑度数全为偶数的情况，显然可以发现连通块之间互不干扰，那么我们对每个连通块进行分析，我们可以把块中的白边当作两条边加入，加入后节点度数奇偶性不受影响，并且添加完边后块内一定联通，根据欧拉回路的性质，我们一定能做到从一个点开始不重复地走过这些边，并最终回到这个点。也就是说每个块对答案的贡献不超过 1，而显然只有在块内全是白点时贡献为 0，这个我们可以特判解决。

修改操作也很简单，直接修改这条边对应点的度数，相应地修改答案，单次操作复杂度可以控制在 O(1) 时间内完成。

初始化用并查集解决，总复杂度 O(n\log_{2}{n} )。

代码很丑。

#include<bits/stdc++.h>
using namespace std;
template <typename T>
void in(T &x){
    char c=getchar(), f=1;
    while ((c<'0' || c>'9') && c!='-') c=getchar();
    if (c=='-') f=-1, c=getchar();
    for (x=0; c>='0' && c<='9'; c=getchar())
        x=x*10+c-'0';
    x*=f;
}
const int N=1e6+5;
struct node{
    int u,v,col;
}eg[N];
int n,m,fa[N],du[N],q,opt,x,ans,al,sz[N],f[N],g[N];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int x1=find(x),y1=find(y);
    if(x1==y1)return ;
    fa[x1]=y1;
    sz[y1]+=sz[x1];
}
int main(){
//  freopen("P10777.in","r",stdin);
//  freopen("P10777.out","w",stdout);
    in(n);in(m);
    for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;;
    for(int i=1;i<=m;i++){
        in(eg[i].u);in(eg[i].v);in(eg[i].col);
        if(eg[i].col==1){du[eg[i].u]++;du[eg[i].v]++;}
        merge(eg[i].u,eg[i].v);
    }
    for(int i=1;i<=n;i++){
        al+=du[i]&1;
        g[find(i)]+=du[i]==0;
    }
    for(int i=1;i<=n;i++){
        if(!f[find(i)]){
            f[find(i)]=1;
            ans++;
            if(g[find(i)]==sz[find(i)])ans--;
        }
    }
    in(q);
    while(q--){
        in(opt);
        if(opt==1){
            in(x);x++;
            if(eg[x].col==1){
                du[eg[x].u]--,du[eg[x].v]--;
                if(du[eg[x].u]==0){
                    g[find(eg[x].u)]++;
                }
                if(du[eg[x].v]==0){
                    g[find(eg[x].u)]++;
                }
                if(g[find(eg[x].u)]==sz[find(eg[x].u)])ans--;
            }
            else{
                du[eg[x].u]++,du[eg[x].v]++;
                if(du[eg[x].u]==1){
                    if(g[find(eg[x].u)]==sz[find(eg[x].u)])ans++;
                    g[find(eg[x].u)]--;

                }
                if(du[eg[x].v]==1){
                    g[find(eg[x].u)]--;
                }
            }
            if(du[eg[x].u]&1)al++;
            else al--;
            if(du[eg[x].v]&1)al++;
            else al--;
            eg[x].col^=1;
        }
        if(opt==2){
            if(al)printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}
/*
按连通块考虑
一次操作,因为一定有进有出,而且要求起点和终点相同,所以度数的奇偶性不变化
把黑边对度数的贡献记为1,白边贡献记为0
有度数为奇数的点直接输出无解

那么此时度数全为偶数,把白边当作两条相同的边加入,显然不影响度数的奇偶性,
而且由于这是一个连通块,当把所有白边都加入后,局部一定是联通图
根据欧拉回路的性质,一定可以以任意一个块内点为起点,不重复地走完这些边
因此把一个联通块全刷成白色至多需要一次操作
还可以发现,只有在该连通块内的边全为白色时,不需要进行操作,这个可以特判

那么我们只需要在进行每次操作1时,修改这条边所连两个点的度数信息,进而更新答案即可
*/