Bzoj3706 反色刷

Posted by yjjr's blog on February 6, 2018

标签:欧拉图,并查集

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

6 6

1 2 1

2 3 1

1 3 1

4 5 1

5 6 1

4 6 1

14

2

1 0

2

1 1

1 2

2

1 3

1 4

1 5

2

1 3

1 4

1 5

2

Sample Output

2

-1

1

0

1

HINT

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

 

分析:如果存在一点黑边度数为奇数,那么肯定无解,输出-1,如果有解的话,统计下有多少个含有黑边的联通子块就可以了,用并查集维护,否则可能会TLE

 

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
#define reg(x) for(int i=head[x];i;i=e[i].next)
using namespace std;
inline LL read()
{
	LL f=1,x=0;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;
}
const int maxn=1e6+6;
LL n,m,q,ans,cnt=0,r1,r2,x,y;
LL fa[maxn],u[maxn],v[maxn],c[maxn],d[maxn],sum[maxn];
inline LL find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
	n=read(),m=read();
	rep(i,1,n)fa[i]=i;
	rep(i,1,m){
		u[i]=read(),v[i]=read(),c[i]=read();
		r1=find(u[i]),r2=find(v[i]);
		if(r1!=r2){
			fa[r1]=r2;
			if(sum[r2]&&sum[r1])ans--;
			sum[r2]+=sum[r1];
		}
		if(c[i]){
			sum[r2]++;
			if(sum[r2]==1)ans++;
			d[u[i]]++,d[v[i]]++;
			if(d[u[i]]&1)cnt++;else cnt--;
			if(d[v[i]]&1)cnt++;else cnt--;
		}
		else if(r1!=r2&&sum[r1]&&sum[r2])ans--;
	}
	q=read();
	rep(i,1,q){
		x=read();
		if(x==1){
			y=read();y++;
			c[y]^=1;r1=find(u[y]);
			if(c[y]){
				sum[r1]++;
				if(sum[r1]==1)ans++;
				d[u[y]]++,d[v[y]]++;
				if(d[u[y]]&1)cnt++;else cnt--;
				if(d[v[y]]&1)cnt++;else cnt--;
			}
			else{
				sum[r1]--;if(sum[r1]==0)ans--;
				d[u[y]]--,d[v[y]]--;
				if(d[u[y]]&1)cnt++;else cnt--;
				if(d[v[y]]&1)cnt++;else cnt--;
			}
		}
		else{
			if(cnt)cout<<"-1\n";
			else printf("%lld\n",ans);
		}
	}
	return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr