二分圖最大匹配 (2)

1、二分圖最大匹配 2006 12 191引例N 項工作分配給N 個人去做，以知每個人可以完成的工作列表，其中每人只能從事一項工作，每項工作只能由一人來完成。問怎樣才能完成盡可能多的工作？ 工作列表：A： x yB： y zC ： x其中ABC為工作人員；xyz為工作。2相關(guān)定義設(shè)G=V, E是一個無向圖。如頂點集V可分割為兩個不相交的子集X和Y，并且圖中每條邊連接的兩個頂點都屬于兩個不同的子集，則稱圖G為二分圖。給定一個二分圖G，在G中若干邊組成的集合M中，任意兩條邊都不與同一個頂點相連，則稱M是G的一個匹配。其中邊數(shù)最多的匹配叫做二分圖的最大匹配。3azyxcbazyxcb普通匹配 (a, x

2、), (b, y) azyxcb最大匹配： (a, y), (b, z), (c, x) 4求二分圖的最大匹配網(wǎng)絡(luò)流算法：匈牙利算法：尋找關(guān)于當(dāng)前匹配的增廣路徑，然后沿增廣路徑進(jìn)行增廣，將得到一個更大的匹配，重復(fù)這一過程，直到找不到增廣路徑時停止。5增廣路徑關(guān)于M的增廣路徑：連接X和Y中兩個未匹配頂點的的路徑，并且該路徑上屬于M和不屬于M的邊交替出現(xiàn)。增廣路徑的長度為奇數(shù)，第一條邊和最后一條邊都不屬于M。匹配M上去掉增廣路徑上原屬于M的邊，加入增廣路徑上原不輸入M的邊，將得到一個更大的匹配。重復(fù)以上過程，當(dāng)不存在增廣路徑時，將得到一個最大匹配。6azyxcb原圖azyxcb當(dāng)前匹 配 Mazy

3、xcb增廣路徑：c, x, a, y, b, zazyxcb增廣后的匹配：M M7匈牙利算法的具體實現(xiàn)Boolean型數(shù)組 cu, v表示原圖中u到v之間是否有邊。Boolean型數(shù)組 xk ( yk ) 表示當(dāng)前尋找增廣路徑時X ( Y ) 集合中k點是否訪問過。Linkk ： 如果Linkk0 則邊 ( Linkk, k ) 屬于當(dāng)前匹配8procedure mainwork; 主過程 ans:=0; 匹配的邊數(shù) fillchar( link, sizeof(link), 0 ); 當(dāng)前匹配沒有邊 for k:=1 to n do 為X中k點尋找匹配邊 fillchar(x, sizeof

4、(x), false); fillchar(y, sizeof(y), false); 開始XY都未訪問 if find(k) then inc(ans); 找到合適的邊 writeln(ans); for k:=1 to n do if linkk0 then writeln(linkk, ,k); 輸出匹配 9function find(v:integer):boolean; 尋找增廣路徑 if xv then exit(false); 已經(jīng)訪問過v點 xv:=true; for i:=1 to n do 尋找沒訪問過 if cv,i and not yi then 的Y中的點 yi:=t

5、rue; if (linki=0) or find(linki) linki:=v; exit(true); 找到增廣路徑 exit(false); 沒找到增廣路徑 10引例分析若a可以完成x, y兩項工作，則連 (a, x), (a, y) 兩條邊最后求該圖的最大匹配。azyxcb11超級英雄現(xiàn)在電視臺有一種節(jié)目叫做超級英雄，大概流程就是每位選手到臺上回答主持人的若干個問題，然后根據(jù)回答問題的多少獲得不同數(shù)目的獎品或獎金主持人總是準(zhǔn)備了若干道題目，只有當(dāng)選手正確回答一道題目后，才能進(jìn)入下一題，否則就被淘汰為了增加節(jié)目的趣味性并適當(dāng)降低難度，主持人總提供給選手幾個“錦囊妙計”，比如求助現(xiàn)場觀眾，或者去掉若干個錯誤答案（選擇題）等12這里，我們把規(guī)則稍微改變一下假設(shè)主持人一共有道題目，選手有種不同的”錦囊妙計”主持人規(guī)定，每道題目都可以從兩種錦囊妙計中選擇一種，而每種錦囊妙計只能使用一次我們又假設(shè)一道題目用了他允許的錦囊妙計后，就一定能夠正確回答，順利進(jìn)入下一題現(xiàn)在我來到