二分圖最大匹配 (2)

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

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

3、xcb增廣路徑：c, x, a, y, b, zazyxcb增廣后的匹配：M M7匈牙利算法的具體實現Boolean型數組 cu, v表示原圖中u到v之間是否有邊。Boolean型數組 xk ( yk ) 表示當前尋找增廣路徑時X ( Y ) 集合中k點是否訪問過。Linkk ： 如果Linkk0 則邊 ( Linkk, k ) 屬于當前匹配8procedure mainwork; 主過程 ans:=0; 匹配的邊數 fillchar( link, sizeof(link), 0 ); 當前匹配沒有邊 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); 已經訪問過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超級英雄現在電視臺有一種節(jié)目叫做超級英雄，大概流程就是每位選手到臺上回答主持人的若干個問題，然后根據回答問題的多少獲得不同數目的獎品或獎金主持人總是準備了若干道題目，只有當選手正確回答一道題目后，才能進入下一題，否則就被淘汰為了增加節(jié)目的趣味性并適當降低難度，主持人總提供給選手幾個“錦囊妙計”，比如求助現場觀眾，或者去掉若干個錯誤答案（選擇題）等12這里，我們把規(guī)則稍微改變一下假設主持人一共有道題目，選手有種不同的”錦囊妙計”主持人規(guī)定，每道題目都可以從兩種錦囊妙計中選擇一種，而每種錦囊妙計只能使用一次我們又假設一道題目用了他允許的錦囊妙計后，就一定能夠正確回答，順利進入下一題現在我來到