13二分匹配及其應(yīng)用

1、ACM程序設(shè)計(jì)8/18/20221今天，你開始 了嗎？復(fù)習(xí)8/18/20222本周雙星（12）：zhanlang8/18/20223第十三講二分圖及其應(yīng)用（Bipartite Graph）8/18/20224主要內(nèi)容什么是二分圖二分圖的最大匹配匈牙利算法二分圖的最小頂點(diǎn)覆蓋DAG圖的最小路徑覆蓋二分圖的最大獨(dú)立集處理技巧8/18/20225什么是二分圖？如果一個(gè)圖的頂點(diǎn)可以分為兩個(gè)集合X和Y，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合X，另一個(gè)頂點(diǎn)屬于集合Y，則稱該圖為“二分圖”（ Bipartite Graph ）8/18/20226例1：婚配問題男女8/18/20227二分圖的最大匹配在二分圖的應(yīng)

2、用中，最常見的就是最大匹配問題，很多其他的問題都可以通過轉(zhuǎn)化為匹配問題來解決。8/18/20228如何求二分圖的最大匹配呢？8/18/20229經(jīng)典算法：匈牙利算法8/18/202210匈牙利算法(求二分圖最大匹配)談匈牙利算法自然避不開Hall定理Hall定理：對(duì)于二分圖G，存在一個(gè)匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)于X的任意一個(gè)子集A，和A鄰接的點(diǎn)集為T(A)，恒有： |T(A)| = |A| 8/18/202211圖示（1）：男1男2女1女2女3返回8/18/202212圖示（2）：男1男2女1女2女3返回X0=男2V1=男2V2 = T(V1)=女1Y=女1V1=男2，

3、男1V2 =女1Y=女2MME(P)( 其中，P是從x0 y的可增廣道路 )8/18/202213匈牙利算法基本步驟：1任給初始匹配M； 2若X已飽和則結(jié)束，否則進(jìn)行第3步； 3在X中找到一個(gè)非飽和頂點(diǎn)x0， 作V1 x0, V2 ； 4若T(V1) = V2則因?yàn)闊o法匹配而停止，否則任選一點(diǎn)y T(V1)V2； 5若y已飽和則轉(zhuǎn)6，否則做一條從x0 y的可增廣道路P，MME(P)，轉(zhuǎn)2； 6由于y已飽和，所以M中有一條邊(y,z)，作 V1 V1 z, V2 V2 y， 轉(zhuǎn)4； 8/18/202214圖示（3）：男1男2女1女2返回X0=男2V1=男2V2 = T(V1)=女1T(V1) !

4、= V2Y=女1V1=男2，男1V2 =女1T(V1)=V28/18/202215NOTE:真正求二分圖的最大匹配的題目很少，往往做一些簡(jiǎn)單的變化，比如8/18/202216變種1：二分圖的最小頂點(diǎn)覆蓋在二分圖中求最少的點(diǎn)，讓每條邊都至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這就是二分圖的“最小頂點(diǎn)覆蓋”。8/18/202217實(shí) 例 分 析8/18/202218例2：嚴(yán)禁早戀，違者開除！男生女生8/18/202219例3：HDOJ_1150 任務(wù)安排有兩臺(tái)機(jī)器A和B以及N個(gè)需要運(yùn)行的任務(wù)。每臺(tái)機(jī)器有M種不同的模式，而每個(gè)任務(wù)都恰好在一臺(tái)機(jī)器上運(yùn)行。如果它在機(jī)器A上運(yùn)行，則機(jī)器A需要設(shè)置為模式ai,如果它在機(jī)器

5、B上運(yùn)行，則機(jī)器A需要設(shè)置為模式bi。每臺(tái)機(jī)器上的任務(wù)可以按照任意順序執(zhí)行，但是每臺(tái)機(jī)器每轉(zhuǎn)換一次模式需要重啟一次。請(qǐng)合理為每個(gè)任務(wù)安排一臺(tái)機(jī)器并合理安排順序，使得機(jī)器重啟次數(shù)盡量少。ACM/ICPC Beijing 20028/18/202220圖示：結(jié)論：二分圖的最小頂點(diǎn)覆蓋數(shù) =二分圖的最大匹配數(shù)a0a1a2a3a4b0b1b2b3b48/18/202221特別說明:此題需要注意的一點(diǎn)，具體參見： 8/18/202222變種2：DAG圖的最小路徑覆蓋用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無環(huán)圖(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。8/18/202223例4：HDOJ_115

6、1 Air Raid有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會(huì)形成回路。你的任務(wù)是編寫程序求最小數(shù)量的傘兵，這些傘兵可以訪問（visit）所有的路口。對(duì)于傘兵的起始降落點(diǎn)不做限制。8/18/202224Input:433 41 32 3Output: 2樣本數(shù)據(jù)：8/18/202225“空襲”示意圖1234432113248/18/202226結(jié)論：DAG圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)（n）- 最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù)8/18/202227變種3:二分圖的最大獨(dú)立集HDOJ_1068 Girls and Boys 大學(xué)二年級(jí)的時(shí)候，一些同

7、學(xué)開始研究男女同學(xué)之間的緣分。研究者試圖找出沒有緣分同學(xué)的最大集。程序的結(jié)果就是要輸出這個(gè)集合中學(xué)生的數(shù)量。8/18/202228樣本數(shù)據(jù)：輸入：70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 1輸出：5 8/18/20222900154326543216“Girls and Boys”示意圖8/18/202230結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)（n） 最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù)8/18/202231Any Questions?8/18/202232相關(guān)練習(xí)201003ACM程序設(shè)計(jì)在線作業(yè)（13）

8、二分匹配8/18/202233附:參考源碼(HDOJ-1150)/*hdoj_1150匈牙利算法 月下版 */#include#include#includeusing namespace std;bool mark1100,mark2100;int list100;int n,m,edge,num;vectorvector v;bool dfs(int to)register int i,point,s = listto;for(i=0;ivs.size();i+)point = vsi;if(!mark2point)continue;mark2point = false;if(listpo

9、int=-1 | dfs(point)listpoint = s;return true;return false; void Solve()int i,j,point;bool flog = false;memset(mark1,true,sizeof(mark1);memset(list,-1,sizeof(list);num=0;for(i=0;in;i+)for(j=0;jvi.size();j+)if(listvij = -1)mark1i = false;listvij = i;num+;if(i=0) flog = true;break; for(i=0;in;i+)if(mark1i)if(!vi.empty()memset(mark2,true,sizeof(mark2);for(j=0;jvi.size();j+)point = vij;if(!mark2point) continue;mark2point = false;if(listpoint = -1 | dfs(point)listpoint = i;num+;break; mark1i = false; if(flog | list0 != -1)cout num-1 endl;else cou