談匈牙利算法自然避不開Hall定理,即是：對于二部圖G,存在一個匹配M,使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對于X的任意一個子集A,和A鄰接的點(diǎn)集為T(A),恒有：│T(A)│ >= │A│
匈牙利算法是基于Hall定理中充分性證明的思想,其基本步驟為：
1．任給初始匹配M；
2．若X已飽和則結(jié)束,否則進(jìn)行第3步；
3．在X中找到一個非飽和頂點(diǎn)x0,作V1 ← {x0},V2 ← Φ；
4．若T(V1) = V2則因?yàn)闊o法匹配而停止,否則任選一點(diǎn)y ∈T(V1)\V2；
5．若y已飽和則轉(zhuǎn)6,否則做一條從x0 →y的可增廣道路P,M←M?E(P),轉(zhuǎn)2；
6．由于y已飽和,所以M中有一條邊(y,z),作 V1 ← V1 ∪{z},V2 ← V2 ∪ {y},轉(zhuǎn)4；
設(shè)數(shù)組up[1..n] --- 標(biāo)記二分圖的上半部分的點(diǎn).
down[1..n] --- 標(biāo)記二分圖的下半部分的點(diǎn).
map[1..n,1..n] --- 表示二分圖的上,下部分的點(diǎn)的關(guān)系.
True-相連,false---不相連.
over1[1..n],over2[1..n] 標(biāo)記上下部分的已蓋點(diǎn).
use[1..n,1..n] - 表示該條邊是否被覆蓋 .
首先對讀入數(shù)據(jù)進(jìn)行處理 ,對于一條邊(x,y) ,起點(diǎn)進(jìn)集合up,終點(diǎn)進(jìn)集合down.標(biāo)記map中對應(yīng)元素為true.
1.尋找up中一個未蓋點(diǎn) .
2.從該未蓋點(diǎn)出發(fā) ,搜索一條可行的路線 ,即由細(xì)邊出發(fā),由細(xì)邊結(jié)束,且細(xì)粗交錯的路線 .
3.若找到 ,則修改該路線上的點(diǎn)所對應(yīng)的over1,over2,use的元素.重復(fù)步驟1.
4.統(tǒng)計use中已覆蓋的邊的條數(shù)total,總數(shù)n減去total即為問題的解.