题解：P10777 BZOJ3706 反色刷

· · 题解

题意：

给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。

现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。 因为某种原因，边的颜色是会改变的，于是……

需要支持以下操作：

  1. 把第 x 反色（编号从 0 \to m-1）
  2. 询问当前图中最少需要多少个反色刷，n,m,q \le 1000000,c<2，没有重边自环。

分析：

一开始就往 dfs 树上去想了，所以没有想到可以用欧拉回路来做。

首先有一个结论，就是对于一个连通块而言，如果每个点连接的黑边数量均为偶数，则有解，反之则必然无解。 这个结论可以用欧拉回路很容易地证明。

还有一个结论就是，若有解，则答案必然等于有黑边的连通块个数。

自己yy出的一个证明就是，你考虑把dfs树构出来，那么每走过一条返祖边，便会对该环上的边的颜色造成影响，反之则不造成影响。显然若我们选出了若干条返祖边，则是可以一次走完的。

题解的证明：首先构造一个可行解，随便找一个有黑度的点，随便走向一个连出的黑边，一直走，直到回到这个点为止（显然一定会回到这个点）。现在考虑在同一个联通块的两个可行路径，设两个路径分别为 u \to \dots \to u 和 v \to \dots \to v，他们的起点必然联通，设这段路径为u_v，则这两个路径可以合并为 u \to u_v \to \dots \to v \to u_v \to u \to \dots \to u。最后一个联通块的所有路径可以合并为一个，证毕。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m,f[N],d[N],bla[N];
struct edge{int x,y,c;}e[N];
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;
} 
int fin(int x){
    if (f[x]==x) return x;
    else return f[x]=fin(f[x]);
}
int main(){
    n=read();m=read();
    for (int i=1;i<=n;i++) f[i]=i;
    int now=0;
    for (int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        e[i].x=x;e[i].y=y;e[i].c=z;
        if (z) now-=d[x]+d[y],d[x]^=1,d[y]^=1,now+=d[x]+d[y];
        if (fin(x)!=fin(y)) f[fin(x)]=fin(y);
    }
    int cnt=0;
    for (int i=1;i<=m;i++)
        if (e[i].c){
            int x=fin(e[i].x);
            if (!bla[x]) cnt++;
            bla[x]++;
        }
    int q=read();
    while (q--){
        int op=read();
        if (op==2) printf("%d\n",now?-1:cnt);
        else{
            int x=read()+1;
            now-=d[e[x].x]+d[e[x].y];d[e[x].x]^=1;d[e[x].y]^=1;now+=d[e[x].x]+d[e[x].y];
            if (e[x].c){
                e[x].c=0;
                bla[fin(e[x].x)]--;
                if (!bla[fin(e[x].x)]) cnt--;
            }else{
                e[x].c=1;
                if (!bla[fin(e[x].x)]) cnt++;
                bla[fin(e[x].x)]++;
            }
        }
    }
    return 0;
}

完结撒花，谢谢！！！