二分圖(匈牙利,KM算法詳解)課件

二分圖匹配二分圖匹配1Bi-partitegraph二分圖的定義：二分圖是這樣的一個(gè)圖，它的頂點(diǎn)可以分為兩個(gè)集合X和Y。所有的邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合X，一個(gè)屬于集合Y。123456二分圖的匹配：給定一個(gè)二分圖G，M為G邊集的一個(gè)子集，如果M滿(mǎn)足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱(chēng)M是一個(gè)匹配。Bi-partitegraph二分圖的定義：123456二2二分圖的最大匹配定義：圖中包含邊數(shù)最多的匹配稱(chēng)為圖的最大匹配。如右圖所示：藍(lán)色部分就構(gòu)成一個(gè)最大匹配，同時(shí)它也是一個(gè)完美匹配完美匹配：如果所有點(diǎn)都在匹配邊上，稱(chēng)這個(gè)最大匹配是完美匹配。

二分圖的最大匹配定義：如右圖所示：藍(lán)色部分3二分圖的最大匹配匈牙利算法（時(shí)間復(fù)雜度O(nm)） 其思想是用寬度優(yōu)先搜索來(lái)找增廣路徑（和floodfill算法類(lèi)似轉(zhuǎn)化為單位容量簡(jiǎn)單網(wǎng)絡(luò)的最大流問(wèn)題在二分圖的基礎(chǔ)上，加入源點(diǎn)s和匯點(diǎn)t，讓s與每個(gè)X結(jié)點(diǎn)連一條邊，每個(gè)Y結(jié)點(diǎn)和t連一條邊，所有弧的容量為1。這樣，飽和弧就對(duì)應(yīng)著匹配邊。二分圖的最大匹配匈牙利算法（時(shí)間復(fù)雜度O(nm)） 4二分圖的最大匹配匈牙利算法：尋找增廣路：初始時(shí)最大匹配為空

for二分圖左半邊的每個(gè)點(diǎn)i

do從點(diǎn)i出發(fā)尋找增廣路徑如果找到，則把它取反（即增加了總了匹配數(shù)）?？匆坏览}：PKU1469二分圖的最大匹配匈牙利算法：5PKU1469一共有N個(gè)學(xué)生跟P門(mén)課程,一個(gè)學(xué)生可以任意選一門(mén)或多門(mén)課,問(wèn)是否達(dá)成: 1.每個(gè)學(xué)生代表的都是不同的課（如果一個(gè)學(xué)生選修的那門(mén)課，那么他就可以代表這門(mén)課） 2.每門(mén)課都有一個(gè)代表PKU1469一共有N個(gè)學(xué)生跟P門(mén)課程,一個(gè)學(xué)6PKU1469輸入為:PN(課程數(shù)跟學(xué)生數(shù))接著有P行,格式為Countstudentistudenti+1……studentcount(Count表示對(duì)課程1感興趣的學(xué)生數(shù),接著有Count個(gè)學(xué)生)如第一行212表示學(xué)生1跟學(xué)生2對(duì)課程1感興趣輸出為:若每門(mén)課都能找到一位代表則輸出”YES”,否則為”NO”P(pán)KU1469輸入為:7PKU1469假如有三個(gè)學(xué)生跟三門(mén)課程,學(xué)生1,2,3.為了跟學(xué)生區(qū)分,假設(shè)3個(gè)課程為4,5,6左邊節(jié)點(diǎn)是學(xué)生,右邊節(jié)點(diǎn)是課程,下圖表示,學(xué)生1對(duì)課程4,5感興趣,學(xué)生2對(duì)課程5,6感興趣,學(xué)生3對(duì)課程6感興趣123456于是問(wèn)題就變?yōu)樵诙謭D中尋找最大匹配,只要這個(gè)最大匹配大于或等于課程數(shù)P,那么就達(dá)到要求了.PKU1469假如有三個(gè)學(xué)生跟三門(mén)課程,學(xué)生1,2,3.為了8尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條邊,假設(shè)找到節(jié)點(diǎn)5,因?yàn)?跟5都還沒(méi)匹配,所以找到一個(gè)匹配.標(biāo)記,xM[1]=5,yM[5]=1;123456假如我們用xM數(shù)組表示左邊節(jié)點(diǎn)對(duì)其右邊節(jié)點(diǎn)的匹配,yM表示右邊節(jié)點(diǎn)對(duì)其左邊節(jié)點(diǎn)的匹配,初始化為-1;現(xiàn)在重點(diǎn)看節(jié)點(diǎn)3,當(dāng)尋找下一條邊時(shí),如圖中的藍(lán)邊,我們發(fā)現(xiàn)節(jié)點(diǎn)6的yM[6]=2;已經(jīng)匹配了.此時(shí)我們就轉(zhuǎn)到節(jié)點(diǎn)6的匹配點(diǎn)2上去,發(fā)現(xiàn)節(jié)點(diǎn)2的另一條邊2->5中節(jié)點(diǎn)5也已經(jīng)匹配了,yM[5]=1;繼續(xù)轉(zhuǎn)到節(jié)點(diǎn)1,發(fā)現(xiàn)節(jié)點(diǎn)1的邊1->4中節(jié)點(diǎn)4還沒(méi)匹配.于是我們找到了一個(gè)增廣路徑增廣路如圖中箭頭所示尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條9123456把圖中紅色線(xiàn)去掉藍(lán)色線(xiàn)加上123456123456找到一個(gè)更好的匹配更改各自的匹配點(diǎn)123456把圖中紅色線(xiàn)去掉藍(lán)色線(xiàn)加上1234561234510總結(jié)所以流程就是:1,對(duì)于一個(gè)未匹配的節(jié)點(diǎn)u,尋找它的每條邊,如果它的邊上的另一個(gè)節(jié)點(diǎn)v還沒(méi)匹配則表明找到了一個(gè)匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點(diǎn)u它邊上的另一個(gè)節(jié)點(diǎn)v已經(jīng)匹配,那么就轉(zhuǎn)向跟v匹配的節(jié)點(diǎn),假設(shè)是w,然后再對(duì)w重復(fù)1,2的步驟,即尋找增廣路.3,假如我們?cè)?,2步過(guò)程中找到一條增廣路,那么修改各自對(duì)應(yīng)的匹配點(diǎn),轉(zhuǎn)步驟4,若無(wú)增廣路,則退出.4,匹配數(shù)+1;總結(jié)所以流程就是:11最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。可以證明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)M簡(jiǎn)單的證明如下：（1）M個(gè)是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個(gè)更大的匹配）（2）M個(gè)是必需的，僅考慮形成最大匹配的這M條邊，由于它們兩兩之間沒(méi)有公共點(diǎn)，因此至少需要M個(gè)點(diǎn)才可以把它們覆蓋

最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合12PKU3041:(類(lèi)似的有PKU3020)

問(wèn)題:假如你現(xiàn)在正處在一個(gè)N*N的矩陣中,這個(gè)矩陣?yán)锩嬗蠯個(gè)障礙物,你擁有一把武器,一發(fā)彈藥一次能消滅一行或一列的障礙物,求最小的彈藥消滅全部障礙物輸入為:NK接下來(lái)有K行,每行包含障礙物的坐標(biāo),即r行c列;如:3411132232輸出為:花費(fèi)最小的彈藥數(shù)PKU3041:(類(lèi)似的有PKU3020)

問(wèn)題:13PKU3041對(duì)于上面那個(gè)數(shù)據(jù)我們可以用下面的表示,0表示無(wú)障礙物,1表示有;101010010首先,我們利用行跟列做二分圖:123123行列如果第i行的第j列有障礙物,則在圖中左邊的i行連一條邊到右邊的j列,上面的數(shù)據(jù)就對(duì)應(yīng)左圖于是問(wèn)題就轉(zhuǎn)化成最小點(diǎn)覆蓋的問(wèn)題.求最大匹配即可.PKU3041對(duì)于上面那個(gè)數(shù)據(jù)我們可以用下面的表示,0表示無(wú)14PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU2226PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU222615DAG圖的最小路徑覆蓋用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問(wèn)題。解決此類(lèi)問(wèn)題可以建立一個(gè)二分圖模型。把所有頂點(diǎn)i拆成兩個(gè)：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m

記住一個(gè)重要的結(jié)論：

DAC圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)看一道例題：PKU1422DAG圖的最小路徑覆蓋用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)(16PKU1422有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會(huì)形成回路。你的任務(wù)是編寫(xiě)程序求最小數(shù)量的傘兵，這些傘兵可以訪(fǎng)問(wèn)（visit）所有的路口。對(duì)于傘兵的起始降落點(diǎn)不做限制。Input:

3

34

13

23Output:2PKU1422有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并3’2’1’132412344’3’2’1’18二分圖的最大獨(dú)立集最大獨(dú)立集問(wèn)題：在Ｎ個(gè)點(diǎn)的圖G中選出m個(gè)點(diǎn)，使這m個(gè)點(diǎn)兩兩之間沒(méi)有邊．求m最大值．記住一個(gè)重要的結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)二分圖的最大獨(dú)立集最大獨(dú)立集問(wèn)題：在Ｎ個(gè)點(diǎn)的圖G中選出m個(gè)19黑色點(diǎn)即為一個(gè)最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少的點(diǎn)，使得剩下的點(diǎn)相互之間沒(méi)有邊。用最少的點(diǎn)去覆蓋所有的邊，也就是最小覆蓋。黑色點(diǎn)即為一個(gè)最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少20二分圖最優(yōu)匹配又稱(chēng)帶權(quán)最大匹配。二分圖的每條邊帶有權(quán)值。求一個(gè)匹配使得匹配邊上的權(quán)值和最大。一般X和Y集合頂點(diǎn)個(gè)數(shù)相同，最優(yōu)匹配也是一個(gè)完備匹配，即每個(gè)頂點(diǎn)都被匹配。如果個(gè)數(shù)不相等，可以通過(guò)補(bǔ)點(diǎn)加0邊實(shí)現(xiàn)轉(zhuǎn)化。最??？看一道例題：PKU2195二分圖最優(yōu)匹配又稱(chēng)帶權(quán)最大匹配。21PKU2195題意：有N個(gè)人跟N個(gè)房子,每個(gè)人跟房子都有一定的距離,現(xiàn)在要讓這N個(gè)人全部回到N個(gè)房子里面去,要求所有人回去的距離最短.現(xiàn)在我們假設(shè)要求的是最大距離.那么就是求最大權(quán)匹配.下面我們先介紹一下KM算法PKU2195題意：22KM算法基本概念：可行頂標(biāo)和相等子圖可行頂標(biāo)：L是一個(gè)關(guān)于結(jié)點(diǎn)的函數(shù)，L(x)是頂點(diǎn)x對(duì)應(yīng)的頂標(biāo)值?？尚许敇?biāo)對(duì)于圖中的每條邊(x,y)都有L(x)+L(y)>=w(x,y)相等子圖：只包含L(x)+L(y)=w(x,y)的邊的子圖KM算法基本概念：可行頂標(biāo)和相等子圖23KM算法定理：如果一個(gè)相等子圖中包含完備匹配，那么這個(gè)匹配就是最優(yōu)匹配證明：由于在算法過(guò)程一直保持頂標(biāo)的可行性，所以任意一個(gè)匹配的權(quán)值和肯定小于等于所有結(jié)點(diǎn)的頂標(biāo)之和，則相等子圖中的完備匹配肯定是最優(yōu)匹配KM算法定理：如果一個(gè)相等子圖中包含完備匹配，那么這個(gè)匹配就24KM算法算法流程設(shè)頂點(diǎn)Xi的頂標(biāo)為a[i]，頂點(diǎn)Yi的頂標(biāo)為b[i]ⅰ.初始時(shí)，a[i]為與Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立ⅱ.當(dāng)相等子圖中不包含完備匹配時(shí)，就適當(dāng)修改頂標(biāo)以擴(kuò)大相等子圖，直到找到完備匹配為止ⅲ.修改頂標(biāo)的方法KM算法算法流程25KM算法當(dāng)從Xi尋找增廣路失敗后，得到一棵交錯(cuò)樹(shù)，它的所有葉子節(jié)點(diǎn)都是X節(jié)點(diǎn)，對(duì)交錯(cuò)樹(shù)中X頂點(diǎn)的頂標(biāo)減少d值，Y頂點(diǎn)的頂標(biāo)增加d值，對(duì)于圖中所有的邊(i,j)，可以看到i和j都不在交錯(cuò)樹(shù)中，邊(i,j)仍然不屬于相等子圖i和j都在交錯(cuò)樹(shù)中，邊(i,j)仍然屬于相等子圖i不在交錯(cuò)樹(shù)中，j在交錯(cuò)樹(shù)中，a[i]+b[j]擴(kuò)大，邊(i,j)不屬于相等子圖KM算法當(dāng)從Xi尋找增廣路失敗后，得到一棵交錯(cuò)樹(shù)，它的所有葉26KM算法i在交錯(cuò)樹(shù),j不在交錯(cuò)樹(shù)中,邊(i,j)有可能加入到相等子圖中為了使a[i]+b[j]>=w(i,j)始終成立,且至少有一條邊加入到相等子圖中,d=min{a[i]+b[j]-w(i,j)},i在交錯(cuò)樹(shù)中,j不在交錯(cuò)樹(shù)中KM算法i在交錯(cuò)樹(shù),j不在交錯(cuò)樹(shù)中,邊(i,j)有可能加入到27假設(shè)有3個(gè)人,我們弄個(gè)簡(jiǎn)化版的.每個(gè)人與家的距離如下圖第一個(gè)人到家1,2,3的距離為3,5,4,第二個(gè)人只能到家1,2距離為2,4,第三個(gè)人只能到家3,距離為7;345247manhome123321假設(shè)有3個(gè)人,我們弄個(gè)簡(jiǎn)化版的.每個(gè)人與家的距離如下圖34528345247manhome123321改變a,b后345247manhome123321ab437010重新匹配左節(jié)點(diǎn)2找到增廣路b010345247manhome123321a437對(duì)左節(jié)點(diǎn)3進(jìn)行匹配345247manhome123321改變a,b后3452429345247manhome123321ab437010345247manhome123321ab336011找到最優(yōu)匹配345247manhome123321改變a,bab336011重新匹配左節(jié)點(diǎn)3,找到增廣路345247manhome123321ab43701034530回到例題:PKU2195題目是說(shuō)有N個(gè)人跟N個(gè)房子,每個(gè)人跟房子都有一定的距離,現(xiàn)在要讓這N個(gè)人全部回到N個(gè)房子里面去,要求所有人回去的距離最短.那么求的就是最小權(quán)匹配了,那么如果我們把所有邊的權(quán)值取反,如圖所示,求其最大匹配,那么結(jié)果就是我們要的了.問(wèn)題解決.345247manhome123321-3-4-5-2-4-7manhome123321回到例題:PKU2195345247manhome1233231練習(xí)題Pku2239,2536Pku3041,1325,2226pku1466Pku1422,2594pku2195練習(xí)題Pku2239,253632THEENDTHEEND33二分圖匹配二分圖匹配34Bi-partitegraph二分圖的定義：二分圖是這樣的一個(gè)圖，它的頂點(diǎn)可以分為兩個(gè)集合X和Y。所有的邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合X，一個(gè)屬于集合Y。123456二分圖的匹配：給定一個(gè)二分圖G，M為G邊集的一個(gè)子集，如果M滿(mǎn)足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱(chēng)M是一個(gè)匹配。Bi-partitegraph二分圖的定義：123456二35二分圖的最大匹配定義：圖中包含邊數(shù)最多的匹配稱(chēng)為圖的最大匹配。如右圖所示：藍(lán)色部分就構(gòu)成一個(gè)最大匹配，同時(shí)它也是一個(gè)完美匹配完美匹配：如果所有點(diǎn)都在匹配邊上，稱(chēng)這個(gè)最大匹配是完美匹配。

二分圖的最大匹配定義：如右圖所示：藍(lán)色部分36二分圖的最大匹配匈牙利算法（時(shí)間復(fù)雜度O(nm)） 其思想是用寬度優(yōu)先搜索來(lái)找增廣路徑（和floodfill算法類(lèi)似轉(zhuǎn)化為單位容量簡(jiǎn)單網(wǎng)絡(luò)的最大流問(wèn)題在二分圖的基礎(chǔ)上，加入源點(diǎn)s和匯點(diǎn)t，讓s與每個(gè)X結(jié)點(diǎn)連一條邊，每個(gè)Y結(jié)點(diǎn)和t連一條邊，所有弧的容量為1。這樣，飽和弧就對(duì)應(yīng)著匹配邊。二分圖的最大匹配匈牙利算法（時(shí)間復(fù)雜度O(nm)） 37二分圖的最大匹配匈牙利算法：尋找增廣路：初始時(shí)最大匹配為空

for二分圖左半邊的每個(gè)點(diǎn)i

do從點(diǎn)i出發(fā)尋找增廣路徑如果找到，則把它取反（即增加了總了匹配數(shù)）?？匆坏览}：PKU1469二分圖的最大匹配匈牙利算法：38PKU1469一共有N個(gè)學(xué)生跟P門(mén)課程,一個(gè)學(xué)生可以任意選一門(mén)或多門(mén)課,問(wèn)是否達(dá)成: 1.每個(gè)學(xué)生代表的都是不同的課（如果一個(gè)學(xué)生選修的那門(mén)課，那么他就可以代表這門(mén)課） 2.每門(mén)課都有一個(gè)代表PKU1469一共有N個(gè)學(xué)生跟P門(mén)課程,一個(gè)學(xué)39PKU1469輸入為:PN(課程數(shù)跟學(xué)生數(shù))接著有P行,格式為Countstudentistudenti+1……studentcount(Count表示對(duì)課程1感興趣的學(xué)生數(shù),接著有Count個(gè)學(xué)生)如第一行212表示學(xué)生1跟學(xué)生2對(duì)課程1感興趣輸出為:若每門(mén)課都能找到一位代表則輸出”YES”,否則為”NO”P(pán)KU1469輸入為:40PKU1469假如有三個(gè)學(xué)生跟三門(mén)課程,學(xué)生1,2,3.為了跟學(xué)生區(qū)分,假設(shè)3個(gè)課程為4,5,6左邊節(jié)點(diǎn)是學(xué)生,右邊節(jié)點(diǎn)是課程,下圖表示,學(xué)生1對(duì)課程4,5感興趣,學(xué)生2對(duì)課程5,6感興趣,學(xué)生3對(duì)課程6感興趣123456于是問(wèn)題就變?yōu)樵诙謭D中尋找最大匹配,只要這個(gè)最大匹配大于或等于課程數(shù)P,那么就達(dá)到要求了.PKU1469假如有三個(gè)學(xué)生跟三門(mén)課程,學(xué)生1,2,3.為了41尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條邊,假設(shè)找到節(jié)點(diǎn)5,因?yàn)?跟5都還沒(méi)匹配,所以找到一個(gè)匹配.標(biāo)記,xM[1]=5,yM[5]=1;123456假如我們用xM數(shù)組表示左邊節(jié)點(diǎn)對(duì)其右邊節(jié)點(diǎn)的匹配,yM表示右邊節(jié)點(diǎn)對(duì)其左邊節(jié)點(diǎn)的匹配,初始化為-1;現(xiàn)在重點(diǎn)看節(jié)點(diǎn)3,當(dāng)尋找下一條邊時(shí),如圖中的藍(lán)邊,我們發(fā)現(xiàn)節(jié)點(diǎn)6的yM[6]=2;已經(jīng)匹配了.此時(shí)我們就轉(zhuǎn)到節(jié)點(diǎn)6的匹配點(diǎn)2上去,發(fā)現(xiàn)節(jié)點(diǎn)2的另一條邊2->5中節(jié)點(diǎn)5也已經(jīng)匹配了,yM[5]=1;繼續(xù)轉(zhuǎn)到節(jié)點(diǎn)1,發(fā)現(xiàn)節(jié)點(diǎn)1的邊1->4中節(jié)點(diǎn)4還沒(méi)匹配.于是我們找到了一個(gè)增廣路徑增廣路如圖中箭頭所示尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條42123456把圖中紅色線(xiàn)去掉藍(lán)色線(xiàn)加上123456123456找到一個(gè)更好的匹配更改各自的匹配點(diǎn)123456把圖中紅色線(xiàn)去掉藍(lán)色線(xiàn)加上1234561234543總結(jié)所以流程就是:1,對(duì)于一個(gè)未匹配的節(jié)點(diǎn)u,尋找它的每條邊,如果它的邊上的另一個(gè)節(jié)點(diǎn)v還沒(méi)匹配則表明找到了一個(gè)匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點(diǎn)u它邊上的另一個(gè)節(jié)點(diǎn)v已經(jīng)匹配,那么就轉(zhuǎn)向跟v匹配的節(jié)點(diǎn),假設(shè)是w,然后再對(duì)w重復(fù)1,2的步驟,即尋找增廣路.3,假如我們?cè)?,2步過(guò)程中找到一條增廣路,那么修改各自對(duì)應(yīng)的匹配點(diǎn),轉(zhuǎn)步驟4,若無(wú)增廣路,則退出.4,匹配數(shù)+1;總結(jié)所以流程就是:44最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)?？梢宰C明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)M簡(jiǎn)單的證明如下：（1）M個(gè)是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個(gè)更大的匹配）（2）M個(gè)是必需的，僅考慮形成最大匹配的這M條邊，由于它們兩兩之間沒(méi)有公共點(diǎn)，因此至少需要M個(gè)點(diǎn)才可以把它們覆蓋

最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合45PKU3041:(類(lèi)似的有PKU3020)

問(wèn)題:假如你現(xiàn)在正處在一個(gè)N*N的矩陣中,這個(gè)矩陣?yán)锩嬗蠯個(gè)障礙物,你擁有一把武器,一發(fā)彈藥一次能消滅一行或一列的障礙物,求最小的彈藥消滅全部障礙物輸入為:NK接下來(lái)有K行,每行包含障礙物的坐標(biāo),即r行c列;如:3411132232輸出為:花費(fèi)最小的彈藥數(shù)PKU3041:(類(lèi)似的有PKU3020)

問(wèn)題:46PKU3041對(duì)于上面那個(gè)數(shù)據(jù)我們可以用下面的表示,0表示無(wú)障礙物,1表示有;101010010首先,我們利用行跟列做二分圖:123123行列如果第i行的第j列有障礙物,則在圖中左邊的i行連一條邊到右邊的j列,上面的數(shù)據(jù)就對(duì)應(yīng)左圖于是問(wèn)題就轉(zhuǎn)化成最小點(diǎn)覆蓋的問(wèn)題.求最大匹配即可.PKU3041對(duì)于上面那個(gè)數(shù)據(jù)我們可以用下面的表示,0表示無(wú)47PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU2226PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU222648DAG圖的最小路徑覆蓋用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問(wèn)題。解決此類(lèi)問(wèn)題可以建立一個(gè)二分圖模型。把所有頂點(diǎn)i拆成兩個(gè)：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m

記住一個(gè)重要的結(jié)論：

DAC圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)看一道例題：PKU1422DAG圖的最小路徑覆蓋用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)(49PKU1422有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會(huì)形成回路。你的任務(wù)是編寫(xiě)程序求最小數(shù)量的傘兵，這些傘兵可以訪(fǎng)問(wèn)（visit）所有的路口。對(duì)于傘兵的起始降落點(diǎn)不做限制。Input:

3

34

13

23Output:2PKU1422有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且50132412344’3’2’1’132412344’3’2’1’51二分圖的最大獨(dú)立集最大獨(dú)立集問(wèn)題：在Ｎ個(gè)點(diǎn)的圖G中選出m個(gè)點(diǎn)，使這m個(gè)點(diǎn)兩兩之間沒(méi)有邊．求m最大值．記住一個(gè)重要的結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)二分圖的最大獨(dú)立集最大獨(dú)立集問(wèn)題：在Ｎ個(gè)點(diǎn)的圖G中選出m個(gè)52黑色點(diǎn)即為一個(gè)最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少的點(diǎn)，使得剩下的點(diǎn)相互之間沒(méi)有邊。用最少的點(diǎn)去覆蓋所有的邊，也就是最小覆蓋。黑色點(diǎn)即為一個(gè)最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少53二分圖最優(yōu)匹配又稱(chēng)帶權(quán)最大匹配。二分圖的每條邊帶有權(quán)值。求一個(gè)匹配使得匹配邊上的權(quán)值和最大。一般X和Y集合頂點(diǎn)個(gè)數(shù)相同，最優(yōu)匹配也是一個(gè)完備匹配，即每個(gè)頂點(diǎn)都被匹配。如果個(gè)數(shù)不相等，可以通過(guò)補(bǔ)點(diǎn)加0邊實(shí)現(xiàn)轉(zhuǎn)化。最??？看一道例題：PKU2195二分圖最優(yōu)匹配又稱(chēng)帶權(quán)最大匹配。54PKU2195題意：有N個(gè)人跟N個(gè)房子,每個(gè)人跟房子都有一定的距離,現(xiàn)在要讓這N個(gè)人全部回到N個(gè)房子里面去,要求所有人回去的距離最短.現(xiàn)在我們假設(shè)要求的是最大距離.那么就是求最大權(quán)匹配.下面我們先介紹一下KM算法PKU2195題意：55KM算法基本概念：可行頂標(biāo)和相等子圖可行頂標(biāo)：L是一個(gè)關(guān)于結(jié)點(diǎn)的函數(shù)，L(x)是頂點(diǎn)x對(duì)應(yīng)的頂標(biāo)值?？尚许敇?biāo)對(duì)于圖中的每條邊(x,y)都有L(x)+L(y)>=w(x,y)相等子圖：只包含L(x)+L(y)=w(x,y)的邊的子圖KM算法基本概念：可行頂標(biāo)和相等子圖56KM算法定理：如果一個(gè)相等子圖中包含完備匹配，那么這個(gè)匹配就是最優(yōu)匹配證明：由于在算法過(guò)程一直保持頂標(biāo)的可行性，所以任意一個(gè)匹配的權(quán)值和肯定小于等于所有結(jié)點(diǎn)的頂標(biāo)之和，則相等子圖中的完備匹配肯定是最優(yōu)匹配KM算法定理：如果一個(gè)相等子圖中包含完備匹配，那么這個(gè)匹配就57KM算法算法流程設(shè)頂點(diǎn)Xi的頂標(biāo)為a[i]，頂點(diǎn)Yi的頂標(biāo)為b[i]ⅰ.初始時(shí)，a[i]為與Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立ⅱ.當(dāng)相等子圖中不包含完備匹配時(shí)，就適當(dāng)修改頂標(biāo)以擴(kuò)大相等子圖，直到找到完備匹配為止ⅲ.修改頂標(biāo)的方法KM算法算法流程58KM算法當(dāng)從Xi尋找增廣路失敗后，得到一棵交錯(cuò)樹(shù)，它的所有葉子節(jié)點(diǎn)都是X節(jié)點(diǎn)，對(duì)交錯(cuò)樹(shù)中X頂點(diǎn)的頂標(biāo)減少d值，Y頂點(diǎn)的頂標(biāo)增加d值，對(duì)于圖中所有的邊(i,j)，可以看到i和j都不在交錯(cuò)樹(shù)中，邊(i,j)仍然不屬于相等子圖i和j都在交錯(cuò)樹(shù)中，邊(i,j)仍然屬于相等子圖i不在交錯(cuò)樹(shù)中，j在交錯(cuò)樹(shù)中，a[i]+b[j]擴(kuò)大，邊(i,j)不屬于相等子圖KM算法當(dāng)從Xi尋找增廣路失敗后，