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