解析

首先大膽猜結論：答案就是最大的點度數

考慮如何構造
設一個點聯通的邊的顏色集合為S，由題意得S中的元素不可重
假設新加入一條邊(u,v)
設$c1=mex(S_u),c2=mex(S_v)$
如果c1等于c2，直接連就行了
否則，把這條邊連成c1，看$S_v$中是否有c1，也就是是否產生矛盾
如果產生矛盾，v有一條連向x的顏色c1的邊，就把這條邊染成c2，再遞歸的看$S_x$中是否有c2…

一種類似于匈牙利的做法

為什么一定有解呢？
考慮什么時候無解
肯定是這個遞歸出現了自相矛盾的地方
比如一開始把（u，v）染成c1，遞歸回來又嘗試把它染成c2
這就強人所難了
但是可以發現，由于我們嘗試染的顏色是交替改變，所以自相矛盾產生的必要條件是出現奇環
眾所周知，二分圖的充要條件是沒有奇環
得證

代碼

代碼利用異或的性質，實現十分優雅

#include<bits/stdc++.h> using namespace std; const int N=2050; const int mod=1e9+7; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,q; int u[N*100],v[N*100]; int du[N]; int col[N][N]; int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);n=read();m=read();q=read();for(int i=1;i<=q;i++){u[i]=read();v[i]=read()+n; du[u[i]]++;du[v[i]]++;}int ans(0);for(int i=1;i<=n+m;i++) ans=max(ans,du[i]);for(int i=1;i<=q;i++){//printf("--------i=%d\n",i);int x=u[i],y=v[i];int c1(1),c2(1);while(col[x][c1]) c1++;while(col[y][c2]) c2++;col[x][c1]=y;col[y][c2]=x;if(c1==c2) continue;for(int c=c2,now=y;now;now=col[now][c],c^=c1^c2){//printf("now=%d\n",now);swap(col[now][c1],col[now][c2]);}}printf("%d\n",ans);for(int i=1;i<=q;i++){for(int j=1;j<=ans;j++){if(col[u[i]][j]==v[i]){printf("%d ",j);break;}}}return 0; } /* */

總結

以上是生活随笔為你收集整理的CF600F：Edge coloring of bipartite graph（二分图、构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。