計算二分圖的算法有網(wǎng)絡(luò)流算法和匈牙利算法（目前就知道這兩種），其中匈牙利算法是比較巧妙的，具體過程如下（轉(zhuǎn)自組合數(shù)學(xué)）：
令g=（x,*,y）是一個二分圖，其中x={x1,x2
},y={y1,y2,.}.令m為g中的任意匹配。
1。將x的所有不與m的邊關(guān)聯(lián)的頂點表上￥，并稱所有的頂點為未掃描的。轉(zhuǎn)到2。
2。如果在上一步?jīng)]有新的標(biāo)記加到x的頂點上，則停，否則 ，轉(zhuǎn)3
3。當(dāng)存在x被標(biāo)記但未被掃描的頂點時，選擇一個被標(biāo)記但未被掃描的x的頂點，比如xi，用（xi）標(biāo)
記y 的所有頂點，這些頂點被不屬于m且尚未標(biāo)記的邊連到xi。
現(xiàn)在頂點xi 是被掃描的。如果不存在被標(biāo)記但未被掃描的頂點，轉(zhuǎn)4。
4。如果在步驟3沒有新的標(biāo)記被標(biāo)記到y(tǒng)的頂點上，則停，否則轉(zhuǎn)5。
5。當(dāng)存在y被標(biāo)記但未被掃描的頂點時。選擇y的一個被標(biāo)記但未被掃描的頂點，比如yj，
用（yj）標(biāo)記x的頂點，這些頂點被屬于m且尚未標(biāo)記的邊連到y(tǒng)j。現(xiàn)在，頂點yj是被掃描的。
如果不存在被標(biāo)記但未被掃描的頂點則轉(zhuǎn)道2。
由于每一個頂點最多被標(biāo)記一次且由于每一個頂點最多被掃描一次，本匹配算法在有限步內(nèi)終止。
匈牙利算法思想:
今天剛看了二分匹配..以前的沒怎么好好想過，今天看了下，其實很簡單..就是不斷找增廣路
過程...有x,y兩個集合，對x這個集合每個點遍歷一遍，遍歷當(dāng)前點時，如果y中有個未匹配的點
，直接跳出,ans++,如果在y中所有和x的點都匹配過，則對這些點再找，如果有其他的路，則
更新，ans++，如果沒，則把當(dāng)前的點置為匹配的點，ans不變..x++;
相關(guān)題目:
http://acm.hdu.edu.cn/showproblem.php?pid=1151http://acm.hdu.edu.cn/showproblem.php?pid=1068http://acm.hdu.edu.cn/showproblem.php?pid=1150http://acm.hdu.edu.cn/showproblem.php?pid=1281http://acm.hdu.edu.cn/showproblem.php?pid=1498http://acm.hdu.edu.cn/showproblem.php?pid=1528http://acm.hdu.edu.cn/showproblem.php?pid=1507相關(guān)知識:
二分圖的最小頂點覆蓋=二分圖的最大匹配數(shù)
二分圖的最大獨立集=頂點數(shù)-二分圖的最大匹配數(shù)
二分圖的最小路徑覆蓋=頂點數(shù)-二分圖的最大匹配數(shù)
posted on 2008-07-31 15:56
小果子 閱讀(693)
評論(0) 編輯 收藏 引用