本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。

問題簡介


　　設(shè)G=(V,E)是一個無向圖。如頂點集V可分割為兩個互不相交的子集V1,V2之并，并且圖中每條邊依附的兩個頂點都分屬于這兩個不同的子集。則稱圖G為二分圖。二分圖也可記為G=(V1,V2,E)。
　　給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。
　　選擇這樣的子集中邊數(shù)最大的子集稱為圖的最大匹配問題(maximal matching problem)
　　如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，，也稱作完備匹配。
算法描述


　　在介紹匈牙利算法之前還是先提一下幾個概念，下面M是G的一個匹配。
　　M-交錯路：p是G的一條通路，如果p中的邊為屬于M中的邊與不屬于M但屬于G中的邊交替出現(xiàn)，則稱p是一條M-交錯路。如：路徑(X3,Y2,X1,Y4)，(Y1,X2,Y3)。
　　M-飽和點：對于v∈V(G)，如果v與M中的某條邊關(guān)聯(lián)，則稱v是M-飽和點，否則稱v是非M-飽和點。如X1，X2，Y1，Y2都屬于M-飽和點，而其它點都屬于非M-飽和點。
　　M-可增廣路：p是一條M-交錯路，如果p的起點和終點都是非M-飽和點，則稱p為M-可增廣路。如(X3,Y2,X1,Y4)。（不要和流網(wǎng)絡(luò)中的增廣路徑弄混了）
　　求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的時間復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。下面介紹用增廣路求最大匹配的方法(稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)。
　　增廣路的定義(也稱增廣軌或交錯軌)：
　　若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬于M的邊和不屬于M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。
　　由增廣路的定義可以推出下述三個結(jié)論：
　　1－P的路徑個數(shù)必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。
　　2－將M和P進行取反操作可以得到一個更大的匹配M’。
　　3－M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。
　　算法輪廓：
　　(1)置M為空
　　(2)找出一條增廣路徑P，通過異或操作獲得更大的匹配M’代替M
　　(3)重復(fù)(2)操作直到找不出增廣路徑為止
時間空間復(fù)雜度


　　時間復(fù)雜度 鄰接矩陣：最壞為O(n^3) 鄰接表：O(mn)

　　空間復(fù)雜度 鄰接矩陣：O(n^2) 鄰接表：O(m+n)

#include<fstream> using namespace std; ifstream fin("dmnd.in"); ofstream fout("dmnd.out"); const int N=1000; int n1,n2; bool state[N+1]; bool find(int x) { for (int i=1;i<=n2;i++) { if (!state[i]&&map[x][i]) { state[i]=1; if (mtch[i]==-1||find(mtch[i])) { mtch[i]=x; return true; } } } return false; } int main() { fin>>n1>>n2>>m; int x,y; for (int i=1;i<=m;i++) { fin>>x>>y; map[x][y]=1; map[y][x]=1; } for (int i=1;i<=n1;i++) { if (find(i)) { memset(state,0,n2); ans++; } } fout<

  本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。