6905. 【2020.11.28提高组模拟】T4 网络(network)

Description

更新： 改为  

Input

第一行两个整数 n,m。

接下来m行，每行两个整数xi,yi。

Output

第一行一个字符串 YES或 NO如果输出为YES接下来输出一个只包含 0或 1的字符串， 第 i个字符为0 表示状态为向上，为 1表示状态为向 下。

Data Constraint

Limit

时间限制： 1s

空间限制： 512MB

Solution

大胆猜想答案一定是YES。

看到 容易想到两两分组，刚开始另（1,2）一组，（3,4）一组....以此类推，如果n是奇数则n自己一组。一组（x,y）表示在经过前若干导线之后要么x中有电流，要么y中有电流。组与组之间互不影响。

先顺着推一遍。

经过一个导线（x,y）后，如果之前的分组为 (x) , (y,z)，则调整为 (x,y) , (z)，如果是 (x,u) , (y,v) 则调整为 (x,y) , (u,v) 考虑所有情况容易发现这样并不会出错。

构造只需要反推即可。

先在所有组中任意选择一条导线有电流，另一条一定没有电流（这里同一组中可能是通过他们之间有导线而调整得来，也有可能是从来没有调整过，但都不影响我们令它们中只能有一根导线有电）

分两种情况讨论：

1.  对于当前一条从后往前的导线 (x,y),调整之后为(x,y) , (z) ,调整之前的可以记录下来 (x,z) ,(y) 或 (y,z) ,(x) ，其中通电情况有2种 ，其中z是一定有电的，x没电y有电或y没有x有电

     此时找出调整前自己一个集合的是x还是y，即为now（此时now一定有电）

     a.如果调整前now为x且调整后 x 没有电   或者  调整前now为y且调整后y任然有电  ，都说明x的电输给了y。答案为1。

     b.否则答案为0。

2. 对于当前一条从后往前的导线 (x,y),调整之后为(x,y) , (u,v) ,调整之前的有两种情况(x,u),(y,v)或(x,v),(y,u) 其中通电情况有4种，其中 u和v的通电情况不变，x和y可能改变， 每一组中只能有一根导线有电。

    a.如果调整后y有电，则答案为1。

    b.否则答案为0。

注意每枚举完一根导线要更新它们的通电情况，才能继续往前更新。

Code 

#include<cstdio> 
#define I int
#define X x[i]
#define Y y[i]
#define F(i,a,b) for(register I i=a;i<=b;i++)
#define Fd(i,a,b) for(register I i=a;i>=b;i--)
#define M 5000005
using namespace std;
I n,m,x[M],y[M],ans[M],f[M/10],sz[M/10],now;
bool bz[M/10];
struct node{I x,fx,y,fy;}s[M];
I R(I &x){
	x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
}
I main(){
	freopen("network.in","r",stdin);
	freopen("network.out","w",stdout);
	R(n),R(m);
	F(i,1,m) R(X),R(Y);
	F(i,1,n) bz[i]=1;
	for(register I i=1;i<=n;i+=2) sz[i]=sz[i+1]=2,f[i]=i+1,f[i+1]=i;
	if(n&1) f[n]=n,sz[n]=1;
	F(i,1,m){
		s[i]=node{X,f[X],Y,f[Y]};
		if(sz[X]+sz[Y]==3){
			if(sz[X]==1){
				sz[f[Y]]=1,sz[X]=sz[Y]=2;
				f[f[Y]]=f[Y],f[X]=Y,f[Y]=X;
			}
			else{
				sz[f[X]]=1,sz[X]=sz[Y]=2;
				f[f[X]]=f[X];f[X]=Y,f[Y]=X;
			}
		}
		else{
			f[f[X]]=f[Y],f[f[Y]]=f[X];
			f[X]=Y,f[Y]=X;
		}
	}
	F(i,1,n){bz[f[i]]=0,bz[i]=1;}
	Fd(i,m,1){
		if(s[i].x==s[i].fx||s[i].y==s[i].fy){
			now=s[i].x==s[i].fx?s[i].x:s[i].y;
			ans[i]=(now==X&&!bz[X])|(now==Y&&bz[Y]);
			if(now==X&&!bz[X]) bz[X]^=1,bz[Y]=0;
			if(now==Y&&!bz[Y]) bz[Y]^=1,bz[X]=0;
		}
		else{
			ans[i]=bz[Y];
			if(!bz[s[i].fx]&&bz[Y]||!bz[s[i].fy]&&bz[X]) bz[X]^=1,bz[Y]^=1;
		}
	}
	printf("YES\n");
	F(i,1,m) printf("%d",ans[i]);
	return 0;
}