欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[BZOJ5303][tarjan]HAOI2018:反色游戏

程序员文章站 2022-05-27 16:22:19
...

BZOJ5303

这题肯定是有关连通性的,考虑一个连通块,如果里面有偶数个黑点,则可以让它们两两组合,如果有奇数个就无解
如果是一棵树那么就只有一组解,加入非树边时异或一下就得到另一组解
所以一个连通块的ans=2mn+1ans=2^{m-n+1}
删点就考虑一下它是不是割点就好了

Code:

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int N=100005;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
int n,m;
int sum,dcc,in[N],fa[N],dfn[N],low[N];
int sign,bel[N],rt,mi[N],val[N];
bool pt[N],col[N],w[N],tag[N],v[N];
int vis[N<<1],nxt[N<<1],head[N<<1],c[N<<1],cnt;
char s[N];
inline void add(int u,int v){vis[++cnt]=v;nxt[cnt]=head[u];c[cnt]=0;head[u]=cnt;}
void tarjan(int x,int e){
	dfn[x]=low[x]=++sign;
	w[x]=col[x];bel[x]=rt;pt[x]=0;
	for(int i=head[x];i;i=nxt[i]){
		if(i==(e^1)) continue;
		if(!dfn[vis[i]]){
			val[x]++;c[i]=c[i^1]=1;fa[vis[i]]=x;
			tarjan(vis[i],i);
			w[x]^=w[vis[i]];low[x]=min(low[x],low[vis[i]]);
			if(!e) continue;
			if(low[vis[i]]>=dfn[x]) pt[x]=1;
			else{
				c[e^1]=0;
				if(tag[x]) c[i]=0,v[x]^=w[vis[i]];
				else tag[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[vis[i]]);
	}
}
inline int get_ans(int x);
inline void init(){
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(in,0,sizeof(in));
	memset(fa,0,sizeof(fa));
	memset(val,0,sizeof(val));
	memset(tag,0,sizeof(tag));
	memset(v,0,sizeof(v));
	sign=sum=dcc=0;cnt=1;
}
int main(){
	int t=read();
	while(t--){
		init();
		n=read();m=read();
		mi[0]=1;
		for(int i=1;i<=m;i++) mi[i]=mi[i-1]*2%mod;
		for(int x,y,i=1;i<=m;i++){
			x=read(),y=read();
			add(x,y);add(y,x);
			in[x]++,in[y]++;
		}
		scanf("%s",s+1);
		for(int i=1;i<=n;i++) col[i]=s[i]-'0';
		for(int i=1;i<=n;i++) if(!dfn[i]){
			++dcc,rt=i,tarjan(i,0);
			sum+=w[rt];
			pt[rt]=(val[rt]>1);
		}	
		cout<<(sum?0:mi[m-n+dcc])<<" ";
		for(int i=1;i<=n;i++) cout<<get_ans(i)<<" ";
		puts("");
	}
	return 0;
}
inline int get_ans(int x){
	if(!in[x]) return (sum-w[x])?0:mi[m-n+dcc];
	if(!pt[x]){
		int tmp=sum;
		if(w[bel[x]]) tmp--;
		if(w[bel[x]]^col[x]) tmp++;
		return tmp?0:mi[m-in[x]-n+1+dcc];
	}
	else{
		int tmp=sum,t=dcc-1;
		if(w[bel[x]]) tmp--;
		for(int i=head[x];i;i=nxt[i])
			if(c[i]){
				if(vis[i]==fa[x]) tmp+=w[bel[x]]^w[x];
				else if(low[vis[i]]<dfn[x]) tmp+=w[vis[i]]^w[bel[x]]^w[x]^v[x];
				else tmp+=w[vis[i]];
				t++;
			}
		return tmp?0:mi[m-in[x]-n+1+t];
	}
}
相关标签: tarjan