轉(zhuǎn)載自：趣寫算法系列之--匈牙利算法-Dark_Scope
博主寫的很好，不贅述了
【書本上的算法往往講得非常復(fù)雜，我和我的朋友計(jì)劃用一些簡(jiǎn)單通俗的例子來(lái)描述算法的流程】
匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見(jiàn)的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。
-------等等，看得頭大？那么請(qǐng)看下面的版本：
通過(guò)數(shù)代人的努力，你終于趕上了剩男剩女的大潮，假設(shè)你是一位光榮的新世紀(jì)媒人，在你的手上有N個(gè)剩男，M個(gè)剩女，每個(gè)人都可能對(duì)多名異性有好感（[圖片上傳失敗...(image-f3f798-1596992782019)]
-_-||暫時(shí)不考慮特殊的性取向），如果一對(duì)男女互有好感，那么你就可以把這一對(duì)撮合在一起，現(xiàn)在讓我們無(wú)視掉所有的單相思（好憂傷的感覺(jué)[圖片上傳失敗...(image-c91c6a-1596992782019)]
），你擁有的大概就是下面這樣一張關(guān)系圖，每一條連線都表示互有好感。
本著救人一命，勝造七級(jí)浮屠的原則，你想要盡可能地撮合更多的情侶，匈牙利算法的工作模式會(huì)教你這樣做：
===============================================================================
一： 先試著給1號(hào)男生找妹子，發(fā)現(xiàn)第一個(gè)和他相連的1號(hào)女生還名花無(wú)主，got it，連上一條藍(lán)線
===============================================================================
二：接著給2號(hào)男生找妹子，發(fā)現(xiàn)第一個(gè)和他相連的2號(hào)女生名花無(wú)主，got it
===============================================================================
三：接下來(lái)是3號(hào)男生，很遺憾1號(hào)女生已經(jīng)有主了，怎么辦呢？
我們?cè)囍o之前1號(hào)女生匹配的男生（也就是1號(hào)男生）另外分配一個(gè)妹子。
(黃色表示這條邊被臨時(shí)拆掉)
與1號(hào)男生相連的第二個(gè)女生是2號(hào)女生，但是2號(hào)女生也有主了，怎么辦呢？我們?cè)僭囍o2號(hào)女生的原配([圖片上傳失敗...(image-a37f11-1596992782019)]
[圖片上傳失敗...(image-f348db-1596992782019)]
)重新找個(gè)妹子(注意這個(gè)步驟和上面是一樣的，這是一個(gè)遞歸的過(guò)程)
此時(shí)發(fā)現(xiàn)2號(hào)男生還能找到3號(hào)女生，那么之前的問(wèn)題迎刃而解了，回溯回去
2號(hào)男生可以找3號(hào)妹子~~~ 1號(hào)男生可以找2號(hào)妹子了~~~ 3號(hào)男生可以找1號(hào)妹子
所以第三步最后的結(jié)果就是：
===============================================================================
四： 接下來(lái)是4號(hào)男生，很遺憾，按照第三步的節(jié)奏我們沒(méi)法給4號(hào)男生騰出來(lái)一個(gè)妹子，我們實(shí)在是無(wú)能為力了……香吉士同學(xué)走好。
===============================================================================
這就是匈牙利算法的流程，其中找妹子是個(gè)遞歸的過(guò)程，最最關(guān)鍵的字就是“騰”字
其原則大概是：有機(jī)會(huì)上，沒(méi)機(jī)會(huì)創(chuàng)造機(jī)會(huì)也要上
【code】
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //掃描每個(gè)妹子
if (line[x][j]==true && used[j]==false)
//如果有曖昧并且還沒(méi)有標(biāo)記過(guò)(這里標(biāo)記的意思是這次查找曾試圖改變過(guò)該妹子的歸屬問(wèn)題，但是沒(méi)有成功，所以就不用瞎費(fèi)工夫了）
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
//名花無(wú)主或者能騰出個(gè)位置來(lái)，這里使用遞歸
girl[j]=x;
return true;
}
}
}
return false;
}
在主程序我們這樣做：每一步相當(dāng)于我們上面描述的一二三四中的一步
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); //這個(gè)在每一步中清空
if find(i) all+=1;
}
匈牙利算法算是一個(gè)比較簡(jiǎn)單算法，但實(shí)際最高復(fù)雜度到達(dá)了n^3
