【JZOJ6206】【20190610】二分图边染色

题目

​ 对一个二分图的边染色，满足有相同端点的边的颜色一定不同;

​ 设最优染色为(C) ，你的染色为(X)，只需要满足$ X le 2^ {lceil log C ceil }$

​ (n_1,n_2 le 10^6 , m le 5 imes 10^5)

题解

• 这题由于没有很好地分析条件，只写了一个(n m sqrt m) 的二分图匹配暴力

• 首先答案应该是(max deg_i)

  证明：

  显然(C ge deg_m)

  设二分图的两部为(X)和(Y)，(deg_m = max deg_i)

  考虑选出(X)部的(deg_i = deg_m)的点，在(Y)部去找到一个完备匹配：
  利用霍尔定理，如果不满足，一定存在(X)选了(x)个(deg_i = deg_m) 的点，但是在(Y)和它们连通的点只有(y)个((y lt x))，根据鸽巢原理，这(y)个点之中一定存在有(deg_j ge lceil frac{x imes deg_m}{y} ceil gt deg_m) ，矛盾

  所以只考虑(deg_m)的点，(X)一定有一个完配(M_x)，(Y)一定有一个完配(M_y)

  考虑$M_x cup M_y $ 形成的若干个连通块，由于所有点的度数<=2，那么一个连通块只能是：

  1. $M_x cap M_y $ 的一条边

  2. 环 (每个点都满足(deg_i =deg_m))

  3. 一条简单路径(只有末尾的某个端点不满足(deg eq deg_m))

     后两者显然都可以调整到满足所有的(deg_i=deg_m)的点都被选入匹配

  所以一次匹配(deg_m)至少-1，重复这样的匹配，即(C le deg_m) ，证毕

• 题意启示我们去二分，可以补出两个虚点使得左右的度数都为偶数

• 做欧拉回路对边染不同的色就可以每次使得(deg_m)折半

  #include<bits/stdc++.h>
  
  using namespace std;
  
  const int N=2000010;
  int n1,n2,n,m,hd[N],o,now,d[N],vis[N],col[N],C;
  struct edge{int u,v,w;}e[N];
  
  char gc(){
  	static char*p1,*p2,s[1000000];
  	if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
  	return(p1==p2)?EOF:*p1++;
  }
  int rd(){
  	int x=0;char c=gc();
  	while(c<'0'||c>'9')c=gc();
  	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
  	return x;
  }
  
  struct Edge{int v,nt,w;}E[N<<1];
  void adde(int u,int v,int w){
  	vis[w]=0;
  	E[o]=(Edge){v,hd[u],w};hd[u]=o++;
  	E[o]=(Edge){u,hd[v],w};hd[v]=o++;
  	d[u]++;d[v]++;
  }
  
  
  void dfs(int u){
  	for(int&i=hd[u];i;i=E[i].nt){
  		if(vis[E[i].w])continue;
  		int tmp=E[i].w;
  		vis[tmp]=1;
  		dfs(E[i].v);
  		now^=1;vis[tmp]=now;
  	}
  }
  
  void solve(int l,int r){
  	o=1;for(int i=l;i<=r;++i)adde(e[i].u,e[i].v,i);
  	int fg=0,cnt=m;
  	d[n+1]=d[n+2]=0;
  	for(int i=l;i<=r;++i){
  		int u=e[i].u,v=e[i].v;
  		if(d[u]>1||d[v]>1)fg=1;
  		if(d[u]&1)adde(u,n+1,++cnt);
  		if(d[v]&1)adde(v,n+2,++cnt);
  		d[u]=d[v]=0;
  	}
  	if(d[n+1]&1)adde(n+1,n+2,++cnt);
  	d[n+1]=d[n+2]=0;
  	if(!fg){
  		++C;hd[n+1]=hd[n+2]=0;
  		for(int i=l;i<=r;++i){
  			col[e[i].w]=C;
  			hd[e[i].u]=hd[e[i].v]=0;
  		}
  		return ;
  	}
  	now=2;
  	for(int i=l;i<=r;++i)if(!vis[i]){
  		dfs(e[i].u);
  	}
  	
  	static edge tmp[N];int p1=l,p2=0,mid;
  	for(int i=l;i<=r;++i)if(vis[i]&1)e[p1++]=e[i];else tmp[++p2]=e[i];
  	mid=p1;for(int i=1;i<=p2;++i)e[p1++]=tmp[i];
  	
  	solve(l,mid-1);
  	solve(mid,r);
  }
  
  int main(){
  	freopen("color.in","r",stdin);
  	freopen("color.out","w",stdout);
  	n1=rd();n2=rd();m=rd();
  	for(int i=1;i<=m;++i){
  		int u=rd(),v=rd();
  		e[i]=(edge){u,v+n1,i};
  	}
  	n=n1+n2;
  	solve(1,m);
  	printf("%d
  ",C);
  	for(int i=1;i<=m;++i)printf("%d
  ",col[i]);
  	return 0;
  }