C++ 匈牙利算法案例分析詳解
匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。
-------等等，看得頭大？那么請看下面的版本：
通過數(shù)代人的努力，你終于趕上了剩男剩女的大潮，假設(shè)你是一位光榮的新世紀媒人，在你的手上有N個剩男，M個剩女，每個人都可能對多名異性有好感（-_-||暫時不考慮特殊的性取向），如果一對男女互有好感，那么你就可以把這一對撮合在一起，現(xiàn)在讓我們無視掉所有的單相思（好憂傷的感覺），你擁有的大概就是下面這樣一張關(guān)系圖，每一條連線都表示互有好感。
本著救人一命，勝造七級浮屠的原則，你想要盡可能地撮合更多的情侶，匈牙利算法的工作模式會教你這樣做：
一： 先試著給1號男生找妹子，發(fā)現(xiàn)第一個和他相連的1號女生還名花無主，got it，連上一條藍線
二：接著給2號男生找妹子，發(fā)現(xiàn)第一個和他相連的2號女生名花無主，got it
三：接下來是3號男生，很遺憾1號女生已經(jīng)有主了，怎么辦呢？
我們試著給之前1號女生匹配的男生（也就是1號男生）另外分配一個妹子。
(黃色表示這條邊被臨時拆掉)
與1號男生相連的第二個女生是2號女生，但是2號女生也有主了，怎么辦呢？我們再試著給2號女生的原配重新找個妹子(注意這個步驟和上面是一樣的，這是一個遞歸的過程)
此時發(fā)現(xiàn)2號男生還能找到3號女生，那么之前的問題迎刃而解了，回溯回去
2號男生可以找3號妹子~~~ 1號男生可以找2號妹子了~~~ 3號男生可以找1號妹子
所以第三步最后的結(jié)果就是：
四： 接下來是4號男生，很遺憾，按照第三步的節(jié)奏我們沒法給4號男生騰出來一個妹子，我們實在是無能為力了……香吉士同學(xué)走好。
這就是匈牙利算法的流程，其中找妹子是個遞歸的過程，最最關(guān)鍵的字就是“ 騰”字
其原則大概是：有機會上，沒機會創(chuàng)造機會也要上
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //掃描每個妹子
if (line[x][j]==true && used[j]==false)
//如果有曖昧并且還沒有標(biāo)記過(這里標(biāo)記的意思是這次查找曾試圖改變過該妹子的歸屬問題，但是沒有成功，所以就不用瞎費工夫了）
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
//名花無主或者能騰出個位置來，這里使用遞歸
girl[j]=x;
return true;
}
}
}
return false;
}
在主程序我們這樣做：每一步相當(dāng)于我們上面描述的一二三四中的一步
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); //這個在每一步中清空
if find(i) all+=1;
}
到此這篇關(guān)于C++ 匈牙利算法案例分析詳解的文章就介紹到這了,更多相關(guān)C++ 匈牙利算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了break的使用for循環(huán)嵌套示例,需要的朋友可以參考下2014-02-02
VC判斷進程是否具有administrator權(quán)限的方法
這篇文章主要介紹了VC判斷進程是否具有administrator權(quán)限的方法,在Windows應(yīng)用程序設(shè)計中具有一定的實用價值,需要的朋友可以參考下2014-10-10
C語言創(chuàng)建和操作單鏈表數(shù)據(jù)結(jié)構(gòu)的實例教程
這篇文章主要介紹了C語言創(chuàng)建和操作單鏈表數(shù)據(jù)結(jié)構(gòu)的實例教程,講解使用C語言實現(xiàn)鏈表結(jié)構(gòu)時指針的使用,需要的朋友可以參考下2016-04-04
本文主要介紹C語言 位域的知識，這里整理了相關(guān)資料，并附示例代碼及詳解，有興趣的小伙伴可以參考下2016-08-08
由于c語言沒有集合類的標(biāo)準庫,需要用時只能自己實現(xiàn),所以本文參考了go語言的slice,找到了一種非常簡化的動態(tài)數(shù)組接口,下面我們就來看看如何在C語言中實現(xiàn)切片吧2024-03-03
本文主要介紹了淺談C++中各種不同意義的new和delete的使用，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
VC++?2019?"const?char*"類型的實參與"LPCTSTR"
這篇文章主要給大家介紹了關(guān)于VC++?2019?"const?char*"類型的實參與"LPCTSTR"類型的形參不兼容的解決方法,文中通過圖文介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2023-03-03
VS Code遠程連接Linux服務(wù)器調(diào)試C程序的操作方法
這篇文章主要介紹了VS Code遠程連接Linux服務(wù)器調(diào)試C程序的操作方法,打開遠程 Linux 服務(wù)器上的文件夾本文以 /root/ 為例,給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-12-12
C++輕松實現(xiàn)字符串與字符數(shù)組的相互轉(zhuǎn)換
本文詳細介紹了如何在C++中通過c_str()和strcpy()函數(shù)將字符串轉(zhuǎn)換為字符數(shù)組,以及使用for循環(huán)、+運算符、重載=和內(nèi)置構(gòu)造函數(shù)將字符數(shù)組轉(zhuǎn)換為字符串的方法,需要的朋友可以參考下2025-03-03
本文主要介紹了C++實現(xiàn)中值濾波的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05