ACM講課之二分圖匹配(匈牙利算法)

二分圖匹配整理ppt什么是二分圖？在離散數(shù)學(xué)中，我們都學(xué)過偶圖，而偶圖就是二分圖。二分圖：給你一個圖，它的頂點可以分為兩個集合，集合V1和V2，所有關(guān)聯(lián)邊的一個頂點在V1中，另一個頂點那么在V2中。v1v2v3v4v5v1v2v3v4二分圖非二分圖整理ppt什么是二分圖匹配？二分圖匹配：給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點，那么稱M是一個匹配。v1v2v3v4v5v1v2v3v4v5匹配1匹配2整理ppt二分圖的最大匹配最大匹配：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。今天我要講的是無權(quán)二分圖的最大匹配問題，采用匈牙利算法。整理ppt匈牙利算法必備知識：1.蓋點：有被M中的邊關(guān)聯(lián)到的節(jié)點，未蓋點那么相反。2.增廣路徑：假設(shè)二分圖中有一條路徑p，其起始點和結(jié)束點都是未蓋點，其間屬于M的邊和不屬于M的邊交替出現(xiàn)，那么稱路徑p是一條關(guān)于M的增廣路徑。匈牙利算法：計算二分圖最大匹配就是應(yīng)用增廣路徑的概念，每次尋找一條關(guān)于M的增廣路徑p，通過M和增廣路徑進行異或，使得M中的匹配數(shù)增加1。以此類推，直至二分圖中不存在關(guān)于M的增廣路徑為止。此時得到匹配M就是圖G的一個最大匹配。注：M為一個邊集，M就是二分圖的匹配整理ppt結(jié)合增廣路徑的定義和以下圖所示，我們可以理解以下結(jié)論：1.增廣路徑的長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2.將M和增廣路徑進行異或操作〔去同存異〕可以得到一個更大的匹配M'。3.M'比M的匹配數(shù)多1。4.M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。核心：判斷當(dāng)前結(jié)點為起點的增廣路徑是否存在。整理pptpoj1274題目大意：有N頭奶牛，M個產(chǎn)奶的棚子，每頭奶牛都有自己想去產(chǎn)奶的幾個棚子，問可以產(chǎn)生的最大匹配數(shù)。數(shù)據(jù)：SampleInput55NM225第一頭：tm2m53234第二頭：tm2m3m4215第三頭：…..3125第四頭：…..12第五頭：…..SampleOutput4整理ppt解題思路：將奶牛看成N集合，棚子看成M集合1,對于N集合中一個未匹配的節(jié)點i,尋找它的每條關(guān)聯(lián)邊,如果它的邊上的另一個節(jié)點j還沒匹配那么說明找到了一個匹配,直接轉(zhuǎn)步驟4;2,假設(shè)節(jié)點i它邊上的另一個節(jié)點j已經(jīng)匹配,那么就轉(zhuǎn)向跟j匹配的節(jié)點，也就是它的前驅(qū),假設(shè)是pre[j],然后再對pre[j]重復(fù)1,2的步驟,即尋找增廣路徑.3,假設(shè)我們在1,2步過程中找到一條增廣路,那么修改各自對應(yīng)的匹配點,轉(zhuǎn)步驟4,假設(shè)無增廣路,那么退出.4,匹配數(shù)+1;整理ppt23455432112345543211整理ppt2345543211i=1時：Pre[2]=1;整理ppt2345543211123i=2時：Pre[5]=1;Pre[2]=2;

整理ppt23455432111i=3時：Pre[1]=3;整理ppt2345543211i=4時：Pre[3]=2;Pre[2]=1;