bzoj 3706: 反色刷 （欧拉图+并查集）

Description

给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。因为某种原因，边的颜色是会改变的，于是。。需要支持以下操作：1 x  把第x条边反色（编号从0~m-1）2   询问当前图中最少需要多少个反色刷

Input

第一行两个整数n m表示这张图有n个点m条边接下来m行 每行3个整数 u v c表示一条无向边和这条边的颜色(0为白色 1为黑色)接下来一个整数q 表示有q个操作接下来q行为操作 描述如上

Output

对于每个询问 输出一行一个整数表示最少需要的反色刷个数 如果没有合法方案输出-1

Sample Input

Sample Output

HINT

100%  n,m,q <= 1000000, c < 2，没有重边自环

Source

题解：欧拉图+并查集

刚开始想的是因为是反色刷，所以刷过的边不能是白色的边，否则又出现了黑色的边。那么就是要求只利用黑边，所形成的图的连通块的个数，发现根本不可做。

因为这根本就是不对的，因为如果刚开始是白边，那么刷两次就可以让他仍然是白边。所以反色刷是有可能刷过白边的。

那么什么情况是无解的呢？就是存在点只考虑黑边的度不是偶数。

为什么呢？因为你要回到起点，并且使所有连通的黑边都被粉刷一次。如果说刷过的路径全是黑边的话，那么就是说图中存在欧拉路径，那么欧拉路径存在的条件就是所有点的度都是偶数。

那么我们如何考虑白边呢？可以发现白边的作用就是连接两个全黑的连通块。而且只要几个全黑的连通块连通，一定存在方案使他们可以一次刷下来。

那么最后的答案其实就是含黑边的连通块个数。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 1000003using namespace std;int fa[N],sum[N],ans,cnt,n,m;int x[N],y[N],c[N],du[N];int find(int x){	if (fa[x]==x) return x;	fa[x]=find(fa[x]);	return fa[x];}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	for (int i=1;i<=n;i++) fa[i]=i;	for (int i=1;i<=m;i++) {		scanf("%d%d%d",&x[i],&y[i],&c[i]);		int r1=find(x[i]); int r2=find(y[i]);		if (r1!=r2) {			if (sum[r1]&&sum[r2]) ans--;			sum[r1]+=sum[r2]; fa[r2]=r1;		}		if (c[i]) {			sum[r1]++; if (sum[r1]==1) ans++;			du[x[i]]++; du[y[i]]++;			if (du[x[i]]&1) cnt++;			else cnt--;			if (du[y[i]]&1) cnt++;			else cnt--; 		}	}	int q; scanf("%d",&q);	for (int i=1;i<=q;i++) {		int opt,now;		scanf("%d",&opt);		if (opt==1) {			scanf("%d",&now); now++;			int r1=find(x[now]);			c[now]^=1;			if (c[now]) {//变成黑边 				sum[r1]++; if (sum[r1]==1) ans++;				du[x[now]]++; du[y[now]]++;			    if (du[x[now]]&1) cnt++;			    else cnt--;			    if (du[y[now]]&1) cnt++;			    else cnt--; 			}			else {				sum[r1]--; if (sum[r1]==0) ans--;				du[x[now]]--; du[y[now]]--;			    if (du[x[now]]&1) cnt++;			    else cnt--;			    if (du[y[now]]&1) cnt++;			    else cnt--; 			}		}		else {			if (cnt) PRintf("-1/n");			else printf("%d/n",ans);		}	}}