P10777 BZOJ3706 反色刷

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

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

1

，而显然只有在块内全是白点时贡献为

0

，这个我们可以特判解决。

修改操作也很简单，直接修改这条边对应点的度数，相应地修改答案，单次操作复杂度可以控制在

O(1)

时间内完成。

初始化用并查集解决，总复杂度

O(n\log_{2}{n} )

。

代码很丑。

CPP

#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时,修改这条边所连两个点的度数信息,进而更新答案即可
*/

P10777 BZOJ3706 反色刷

文章操作

相关推荐

评论

P10777 BZOJ3706 反色刷