溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“C++如何實現匈牙利算法”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“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)
一些題目，乍一看與上面這個男女配對的問題沒有任何相似點，其實都可以用匈牙利算法。例如：
題目描述
小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;
}面對OIBH組織的囂張氣焰, 柯南決定深入牛棚, 一探虛實.
他經過深思熟慮, 決定從OIBH組織大門進入...........
OIBH組織的大門有一個很神奇的鎖.
鎖是由M*N個格子組成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子給按下去.
如果柯南能在組織限定的次數內將所有格子都按下去, 那么他就能夠進入總部. 但是OIBH組織不是吃素的, 他們的限定次數恰是最少次數.
請您幫助柯南計算出開給定的鎖所需的最少次數.
讀入/Input：
第一行 兩個不超過100的正整數N, M表示矩陣的長和寬
以下N行 每行M個數 非0即1 1為凸起方格輸出/Output：
一個整數 所需最少次數
如果我們把樣例的矩陣，轉化為二分圖的形式，是這樣的：
按下一行或一列，其實就是刪掉與某個點相連的所有邊。現在要求最少的操作次數，想想看，這不就是求最小點覆蓋數嗎？所以直接套匈牙利算法即可。代碼略。
描述 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++如何實現匈牙利算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
