【JZOJ4796】三色图 题解

题目大意

  现在你有一个二分图，你有三种颜色0,1,2，然后你要给图上的每一条边染一种颜色（也就是赋予该边一个0,1,2）的边权。我们定义点权 s(u) 为：所有与 u 相连的边的边权之和模三。
  你需要给出一种染色方案，使得对于该图任意一对通过一条边直接相连的点对点权不同。
  点数 n<=1500，边数 m<=10000

【20%】m<=20

  暴力枚举每条边染什么色。

【100%】n<=1500, m<=1e4

  这是一个二分图，因此如果我们处理成左边的点全部为0色，右边的点全部不为0色，就一定满足条件。

  考虑我们在右边任选两个连通的点，然后任选一条以这两个点为起止点的路径，将该路径上的边权按顺序分别加上 1、2、1、2、1、2……这样会发现，只有起止点的点权会改变，中途点的点权都不改变。

  如此我们对于二分图的每个连通块，每次在右边找两个未处理的点，然后把连接这两个点的路径按上述规则加权。（具体实现可以先找一个未处理的点，然后dfs到另一个未处理的点）
  若对于一个连通块，右边的点为奇数？那么多出来的那个点可以跟同连通块的任意一个右点 x 配对，只要从 x 出发时，第一条边加的权是color[x]即可（这样保证 x 最终点权不为 0）。
  若对于一个连通块，右边的点只有一个？把该联通块左右互换一下即可。若互换之后右边还是只有一个点，说明该连通块本身只有左右一对点，那么输出不合法。

代码

略丑不要介意。。。

#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxm=1e4+5;

int n1,n2,m;

int tot,go[2*maxm],bh[2*maxm],next[2*maxm],f1[maxm];
void ins(int x,int y,int z)
{
	go[++tot]=y;
	bh[tot]=z;
	next[tot]=f1[x];
	f1[x]=tot;
}

int fa[maxm];
int get(int x) {return (fa[x]==x) ?x :fa[x]=get(fa[x]) ;}

int bz[maxm],now,ans[maxm],clr[maxm];
int dfs(int ty,int k,int c)
{
	if ((!ty && k>n1 || ty && k<=n1) && !bz[k]) {bz[k]=now; return k;};
	bz[k]=now;
	for(int p=f1[k]; p; p=next[p]) if (bz[go[p]]!=now)
	{
		clr[k]=(clr[k]+c)%3;
		clr[go[p]]=(clr[go[p]]+c)%3;
		ans[bh[p]]=(ans[bh[p]]+c)%3;
		
		int re=dfs(ty,go[p],(c==1)?2:1);
		if (re!=-1) return re;
		
		clr[k]=(clr[k]-c+3)%3;
		clr[go[p]]=(clr[go[p]]-c+3)%3;
		ans[bh[p]]=(ans[bh[p]]-c+3)%3;
	}
	return -1;
}

int main()
{
	scanf("%d %d %d",&n1,&n2,&m);
	fo(i,1,n1+n2) fa[i]=i;
	fo(i,1,m)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		ins(x,y+n1,i), ins(y+n1,x,i);
		fa[get(x)]=get(y+n1);
	}
	
	fo(i,n1+1,n1+n2) if (!bz[i])
	{
		if (!f1[i]) continue;
		bz[i]=++now;
		int j=dfs(0,i,1);
		if (j==-1)
		{
			fo(k,n1+1,n1+n2) if (i!=k && get(k)==get(i)) {j=k; break;}
			if (j>-1)
			{
				now++;
				bz[i]=0;
				dfs(0,j,clr[j]);
			} else
			{
				for(int p=f1[i]; p; p=next[p])
				{
					now++;
					bz[i]=0;
					j=dfs(1,go[p],1);
					break;
				}
				if (j==-1) {printf("No\n"); return 0;}
			}
		}
	}
	
	printf("Yes\n");
	fo(i,1,m) printf("%d ",ans[i]);
}