二分圖的判定
- 如果一個圖是連通的，可以用如下的染色法判定是否二分圖：
- 我們把
X
Y
1
- 從某個未染色的結點
u
BFS
DFS
u
u
v
v
u
u
v
- 如果一個圖不連通，則在每個連通塊中作判定。
#include <bits/stdc++.h> const int maxn = 505; std::vector<int> e[maxn]; int m,n,color[maxn]; bool flag;//全局，标記是否有環 void dfs(int u){ if(flag) return;//如果已經存在環就沒必要接着遞歸了 int len = e[u].size();//省點常數 for(int i = 0; i < len; i++){ //周遊所有相鄰頂點，即連着的點 int v = e[u][i]; if(color[v]==0){//v還未通路，染色并遞歸 color[v] = -color[u]; dfs(v); } else if(color[v]==color[u]){ flag=1;//說明有環 return; } } } void solve(){ for(int i = 0; i < n; i++){ if(color[i] == 0){ color[i] = 1; dfs(i); if(flag){ printf("NOT BICOLORABLE. "); return; } } } printf("BICOLORABLE. "); } int main(){ while(~scanf("%d%d",&n,&m)){ memset(color, 0, sizeof(color)); memset(e, 0, sizeof(e)); for(int i = 0; i < m; i++){ int u,v;scanf("%d%d",&u,&v); e[u].push_back(v);e[v].push_back(u); } solve(); } return 0; }
- 我們把
最大比對 KM
KM
- 頂标：設頂點 (X_i) 的頂标為 (A[i])，頂點 (Y_j) 的頂标為 (B[j]) ，頂點 (X_i) 與 (Y_j) 之間的邊權為 (w[i][j])，初始化時，(A[i]) 的值為與該點關聯的最大邊權值，(B[j]) 的值為
- 相等子圖：選擇 (A[i] + B[j] = w[i][j]) 的邊 (<i, j>) 構成的子圖，就是相等子圖。
- 算法執行過程中，對任一條邊(<i, j>) ，(A[i] + B[j] >= w[i][j]) 恒成立。
-
slack
Y
- 算法圖示：
- 從(X_1) 開始跑匈牙利，比對的條件是：(A[i] + B[j] = w[i][j]) ，顯然 $ X_1$ 和 (Y_3) 比對成功。
- 接着從 (X_2) 開始，(A[X_2]+B[Y_3]==w[X_2][X_3]) ，此時 (Y_3) 已被 (X_1) 比對，嘗試讓 (X_1) 換一個比對對象，但在 (X_1) 的鄰接點沒有滿足：(A[i] + B[j] = w[i][j]) 的點，這些相臨邊和頂标和的最小內插補點為：(minz=1) ，把此時已标記的 (X) 部的頂标減去(minz)，即：(A[x_1]=5-1=4,A[X_2]-1=3) ， (Y) 部的此時标記的頂标加上(minz)，即：(B[y_3]=0+1=1) ，此時(A[X_1]+B[Y_1]==w[X_1][Y_1])。
- 最後從(X_3) 開始找增廣路，(X_3) 比對 (Y_3) ，不滿足，調整頂标，即(A[3]=5-1=4)，比對(Y_3) 成功，嘗試勸說 (X_2) 尋找新的比對，此時 (Y_1) 滿足比對，嘗試讓 (X_1) 尋找新的比對，此時(X_1)已找不到新的為比對的點，比對失敗，回溯到 (X_2) ，
-
Code
#include <bits/stdc++.h> const int maxn = 300 + 10,maxe=1e4+5,Inf = 0x3f3f3f3f; struct Edee{int to,w,next;}e[maxe]; int n,m,len,head[maxn],g[maxn][maxn]; int wx[maxn], wy[maxn];//每個點的頂标值（需要根據二分圖處理出來） int match[maxn];//每個Y部點所比對的X部的點 int visx[maxn], visy[maxn];//每個點是否加入增廣路 int slack[maxn];//邊權和頂标最小的內插補點 void Insert(int u,int v){ e[++len].to=v;e[len].next=head[u];head[u]=len; } bool dfs(int u){//進入DFS的都是X部的點，找到增光路傳回1，否則傳回0 visx[u] = 1;//标記進入增廣路 for(int i = head[u]; i ; i=e[i].next){ int v = e[i].to; if(!visy[v]){//如果Y部的點還沒進入增廣路,并且存在路徑 int t = wx[u] + wy[v] - g[u][v]; if(t == 0){//t為0說明是相等子圖 visy[v] = 1;//加入增廣路 if(match[v] == -1 || dfs(match[v])){ match[v] = u;//進行比對 return 1; } } else if(t > 0)//此處t一定是大于0，因為頂标之和一定>=邊權 slack[v] = std::min(slack[v], t); //slack[v]存的是Y部的點需要變成相等子圖頂标值最小增加多少 } } return false; } int KM(){ memset(match, -1, sizeof(match)); memset(wx, 0, sizeof(wx));//wx的頂标為該點連接配接的邊的最大權值 memset(wy, 0, sizeof(wy));//wy的頂标為0 for(int u = 1; u <= n; u++){//預處理出頂标值 for(int i = head[u]; i ; i=e[i].next) wx[u] = std::max(wx[u], g[u][e[i].to]); } for(int i = 1; i <= n; i++){//枚舉X部的點 memset(slack, 0x3f, sizeof(slack)); while(1){ memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if(dfs(i))break;//已經比對正确 int minz = Inf; for(int j = 1; j <= n; j++) if(!visy[j] && minz > slack[j]) minz = slack[j];//找出還沒經過的點中，需要變成相等子圖的最小額外增加的頂标值 //将X部已通路的頂标減去minz，Y部已通路的頂标加上minz for(int j = 1; j <= n; j++) if(visx[j])wx[j] -= minz; for(int j = 1; j <= n; j++) //修改頂标後，要把所有不在交錯樹中的Y頂點的slack值都減去minz if(visy[j])wy[j] += minz; else slack[j] -= minz;//未在增光路，但相應的X部已通路的頂标減少了,其相鄰的未通路的期望也減小 } } int ans = 0;//二分圖最優比對權值 for(int i = 1; i <= n; i++) if(match[i] != -1)ans += g[match[i]][i]; return ans; } int main(){ while(scanf("%d%d", &n,&m) != EOF){ for(int i = 1; i <= m; i++){ int u,v,w;scanf("%d%d%d", &u,&v,&w); g[u][v]=w;Insert(u,v); } printf("%d ", KM()); } return 0; }