詳解C++實現匈牙利算法
一、匈牙利算法介紹
匈牙利算法(Hungarian algorithm)主要用於解決一些與二分圖匹配有關的問題,所以我們先來瞭解一下二分圖。
二分圖(Bipartite graph)是一類特殊的圖,它可以被劃分為兩個部分,每個部分內的點互不相連。下圖是典型的二分圖。
可以看到,在上面的二分圖中,每條邊的端點都分別處於點集X和Y中。匈牙利算法主要用來解決兩個問題:求二分圖的最大匹配數和最小點覆蓋數。
這麼說起來過於抽象瞭,我們現在從實際問題出發。
二、最大匹配問題
看完上面講的,相信讀者會覺得雲裡霧裡的:這是啥?這有啥用?所以我們把這張二分圖稍微做點手腳,變成下面這樣:
現在Boys和Girls分別是兩個點集,裡面的點分別是男生和女生,邊表示他們之間存在“曖昧關系”。最大匹配問題相當於,假如你是紅娘,可以撮合任何一對有曖昧關系的男女,那麼你最多能成全多少對情侶?(數學表述:在二分圖中最多能找到多少條沒有公共端點的邊)
現在我們來看看匈牙利算法是怎麼運作的:
我們從B1看起(男女平等,從女生這邊看起也是可以的),他與G2有曖昧,那我們就先暫時把他與G2連接(註意這時隻是你作為一個紅娘在紙上構想,你沒有真正行動,此時的安排都是暫時的)。
來看B2,B2也喜歡G2,這時G2已經“名花有主”瞭(雖然隻是我們設想的),那怎麼辦呢?我們倒回去看G2目前被安排的男友,是B1,B1有沒有別的選項呢?有,G4,G4還沒有被安排,那我們就給B1安排上G4。
然後B3,B3直接配上G1就好瞭,這沒什麼問題。至於B4,他隻鐘情於G4,G4目前配的是B1。B1除瞭G4還可以選G2,但是呢,如果B1選瞭G2,G2的原配B2就沒得選瞭。我們繞瞭一大圈,發現B4隻能註定單身瞭,可憐。(其實從來沒被考慮過的G3更可憐)
這就是匈牙利算法的流程,至於具體實現,我們來看看代碼:
int M, N; //M, N分別表示左、右側集合的元素數量 int Map[MAXM][MAXN]; //鄰接矩陣存圖 int p[MAXN]; //記錄當前右側元素所對應的左側元素 bool vis[MAXN]; //記錄右側元素是否已被訪問過 bool match(int i) { for (int j = 1; j <= N; ++j) if (Map[i][j] && !vis[j]) //有邊且未訪問 { vis[j] = true; //記錄狀態為訪問過 if (p[j] == 0 || match(p[j])) //如果暫無匹配,或者原來匹配的左側元素可以找到新的匹配 { p[j] = i; //當前左側元素成為當前右側元素的新匹配 return true; //返回匹配成功 } } return false; //循環結束,仍未找到匹配,返回匹配失敗 } int Hungarian() { int cnt = 0; for (int i = 1; i <= M; ++i) { memset(vis, 0, sizeof(vis)); //重置vis數組 if (match(i)) cnt++; } return cnt; }
其實流程跟我們上面描述的是一致的。註意這裡使用瞭一個遞歸的技巧,我們不斷往下遞歸,嘗試尋找合適的匹配。
三、最小點覆蓋問題
另外一個關於二分圖的問題是求最小點覆蓋:我們想找到最少的一些點,使二分圖所有的邊都至少有一個端點在這些點之中。倒過來說就是,刪除包含這些點的邊,可以刪掉所有邊。
這為什麼用匈牙利算法可以解決呢?你如果以為我要長篇大論很久就錯瞭,我們隻需要一個定理:
(König定理)
一個二分圖中的最大匹配數等於這個圖中的最小點覆蓋數。
好瞭,本節可以結束瞭,我們不是搞數學的,不需要證明。但是提供一個直觀地找最小覆蓋點集的方法:看題圖,從左側一個未匹配成功的點出發,走一趟匈牙利算法的流程(即紫色的箭頭),所有左側未經過的點,和右側經過的點,即組成最小點覆蓋。(即圖中的B3、G2、G4)
對於每個左部節點,尋找增廣路最多遍歷整張二分圖一次,因此,該算法時間復雜度為O(MN)
四、匈牙利算法的應用
一些題目,乍一看與上面這個男女配對的問題沒有任何相似點,其實都可以用匈牙利算法。例如:
4.1、(洛谷P1129) [ZJOI2007]矩陣遊戲
題目描述
小Q是一個非常聰明的孩子,除瞭國際象棋,他還很喜歡玩一個電腦益智遊戲――矩陣遊戲。矩陣遊戲在一個$ N× N $ 黑白方陣進行(如同國際象棋一般,隻是顏色是隨意的)。每次可以對該矩陣進行兩種操作:
行交換操作:選擇矩陣的任意兩行,交換這兩行(即交換對應格子的顏色)
列交換操作:選擇矩陣的任意兩列,交換這兩列(即交換對應格子的顏色)
遊戲的目標,即通過若幹次操作,使得方陣的主對角線(左上角到右下角的連線)上的格子均為黑色。
對於某些關卡,小Q百思不得其解,以致他開始懷疑這些關卡是不是根本就是無解的!於是小Q決定寫一個程序來判斷這些關卡是否有解。
輸入格式
第一行包含一個整數T,表示數據的組數。
接下來包含T組數據,每組數據第一行為一個整數N,表示方陣的大小;接下來N行為一個 $ N× N $的01矩陣(0表示白色,1表示黑色)。
輸出格式
包含T行。對於每一組數據,如果該關卡有解,輸出一行Yes;否則輸出一行No。
我們把矩陣轉化為二分圖(左側集合代表各行,右側集合代表各列,某位置為1則該行和該列之間有邊)。我們想進行一系列交換操作,使得X1連上Y1,X2連上Y2,……
大傢可以想象,所謂的交換,是不是可以等價為重命名?我們可以在保持當前二分圖結構不變的情況下,把右側點的編號進行改變,這與交換的效果是一樣的。
所以想讓X1、X2…與Y1、Y2…一一對應,其實隻需要原圖最大匹配數為4就行瞭。(這與組合數學中相異代表系的概念相合)。代碼如下:
#include <cstdio> #include <cstring> int Map[205][205], p[205], vis[205], N, T; bool match(int i){ for (int j = 1; j <= N; ++j){ if (Map[i][j] && !vis[j]){ vis[j] = 1; if (p[j] == 0 || match(p[j])){ p[j] = i; return true; } } } return false; } int Hungarian(){ int cnt = 0; for (int i = 1; i <= N; ++i){ memset(vis, 0, sizeof(vis)); if (match(i)) cnt++; } return cnt; } int main(){ scanf("%d", &T); while (T--){ scanf("%d", &N); memset(p, 0, sizeof(p)); for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) scanf("%d", &Map[i][j]); puts(Hungarian() == N ? "Yes" : "No"); } return 0; }
4.2、(vijos1204) CoVH之柯南開鎖
面對OIBH組織的囂張氣焰, 柯南決定深入牛棚, 一探虛實.
他經過深思熟慮, 決定從OIBH組織大門進入………..
OIBH組織的大門有一個很神奇的鎖.
鎖是由M*N個格子組成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子給按下去.
如果柯南能在組織限定的次數內將所有格子都按下去, 那麼他就能夠進入總部. 但是OIBH組織不是吃素的, 他們的限定次數恰是最少次數.
請您幫助柯南計算出開給定的鎖所需的最少次數.
讀入/Input:
第一行 兩個不超過100的正整數N, M表示矩陣的長和寬
以下N行 每行M個數 非0即1 1為凸起方格輸出/Output:
一個整數 所需最少次數
如果我們把樣例的矩陣,轉化為二分圖的形式,是這樣的:
按下一行或一列,其實就是刪掉與某個點相連的所有邊。現在要求最少的操作次數,想想看,這不就是求最小點覆蓋數嗎?所以直接套匈牙利算法即可。代碼略。
4.3、(TYVJ P1035) 棋盤覆蓋
描述 Description
給出一張nn(n<=100)的國際象棋棋盤,其中被刪除瞭一些點,問可以使用多少12的多米諾骨牌進行掩蓋。
輸入格式 Input Format
第一行為n,m(表示有m個刪除的格子)
第二行到m+1行為x,y,分別表示刪除格子所在的位置
x為第x行
y為第y列
輸出格式 Output Format
一個數,即最大覆蓋格數
經典的多米諾覆蓋問題大傢都很熟悉,我們把棋盤染色,每個多米諾骨牌恰好覆蓋一個白格和一個黑格(這裡為瞭美觀染成瞭其他顏色,下面仍將其稱作黑格)。
我們刪除瞭一些格子:
現在要求多米諾骨牌最大覆蓋數。
你可能已經看出來瞭,我們在染色之後,黑格和白格可以構成一個二分圖,每個白格都隻和黑格相連,每個黑格也隻和白格相連。在給所有黑格和白格編號後,我們把每個未刪除的格子都與它上下左右緊鄰的未刪除的格子相連。很顯然,這張二分圖的最大匹配數,就是我們能放下最多的多米諾骨牌數。註意因為數據范圍較大,要用鄰接表存圖。
#include <cstdio> #include <cstring> #define MAXN 5500 struct Edges { int to, next; } edges[MAXN * 8]; int Map[105][105], head[MAXN], p[MAXN], vis[MAXN], N, cnt_edge; inline int add(int from, int to) { edges[++cnt_edge].next = head[from]; head[from] = cnt_edge; edges[cnt_edge].to = to; } inline int trans(int i, int j, int n) //把坐標轉化為編號 { return ((i - 1) * n + j + 1) / 2; } bool match(int i) { for (int e = head[i]; e; e = edges[e].next) { int j = edges[e].to; if (!vis[j]) { vis[j] = true; if (p[j] == 0 || match(p[j])) { p[j] = i; return true; } } } return false; } int Hungarian() { int cnt = 0; for (int i = 1; i <= N; ++i) { memset(vis, 0, sizeof(vis)); if (match(i)) cnt++; } return cnt; } int main() { int n, m, x, y; scanf("%d%d", &n, &m); N = (n * n + 1) / 2; memset(Map, -1, sizeof(Map)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) Map[i][j] = 0; for (int i = 0; i < m; ++i) { scanf("%d%d", &x, &y); Map[x][y] = -1; } for (int i = 1; i <= n; i++) for (int j = i % 2 ? 1 : 2; j <= n; j += 2) if (Map[i][j] == 0) { if (Map[i + 1][j] != -1) add(trans(i, j, n), trans(i + 1, j, n)); if (Map[i][j + 1] != -1) add(trans(i, j, n), trans(i, j + 1, n)); if (Map[i - 1][j] != -1) add(trans(i, j, n), trans(i - 1, j, n)); if (Map[i][j - 1] != -1) add(trans(i, j, n), trans(i, j - 1, n)); } printf("%d\n", Hungarian()); return 0; }
以上就是詳解C++實現匈牙利算法的詳細內容,更多關於C++匈牙利算法的資料請關註WalkonNet其它相關文章!