HDUACM13二分匹配及其應(yīng)用谷風(fēng)詳析

《HDUACM13二分匹配及其應(yīng)用谷風(fēng)詳析》由會員分享，可在線閱讀，更多相關(guān)《HDUACM13二分匹配及其應(yīng)用谷風(fēng)詳析（35頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、ACM程序設(shè)計(jì)程序設(shè)計(jì)杭州電子科技大學(xué) 劉春英1特制分析今天，今天，你開始你開始 了嗎？了嗎？復(fù)習(xí)2特制分析本周雙星本周雙星（1 12 2）：）：zhanlangzhanlang3特制分析第十三講第十三講二分圖及其應(yīng)用二分圖及其應(yīng)用（Bipartite Graph）4特制分析主要內(nèi)容主要內(nèi)容n什么是二分圖什么是二分圖n二分圖的最大匹配二分圖的最大匹配n匈牙利算法匈牙利算法n二分圖的最小頂點(diǎn)覆蓋二分圖的最小頂點(diǎn)覆蓋nDAGDAG圖的最小路徑覆蓋圖的最小路徑覆蓋n二分圖的最大獨(dú)立集二分圖的最大獨(dú)立集n處理技巧處理技巧5特制分析什么是二分圖？什么是二分圖？n如果一個(gè)圖的頂點(diǎn)可以分為兩個(gè)集合如果一個(gè)圖

2、的頂點(diǎn)可以分為兩個(gè)集合X X和和Y Y，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合合X X，另一個(gè)頂點(diǎn)屬于集合，另一個(gè)頂點(diǎn)屬于集合Y Y，則稱該圖，則稱該圖為為“二分圖二分圖”（ Bipartite Graph Bipartite Graph ）6特制分析例例1 1：婚配問題：婚配問題男男女女7特制分析二分圖的最大匹配二分圖的最大匹配在二分圖的應(yīng)用中，最常見的就是在二分圖的應(yīng)用中，最常見的就是最大匹配最大匹配問題，很多其他的問題都可以通過轉(zhuǎn)化為匹問題，很多其他的問題都可以通過轉(zhuǎn)化為匹配問題來解決。配問題來解決。8特制分析如何求二分圖的最大如何求二分圖的最大匹配呢？匹配

3、呢？9特制分析經(jīng)典算法：經(jīng)典算法：匈牙利算法匈牙利算法10特制分析匈牙利算法匈牙利算法( (求二分圖最大匹配求二分圖最大匹配) )n談匈牙利算法自然避不開談匈牙利算法自然避不開HallHall定理定理nHallHall定理：對于二分圖定理：對于二分圖G G，存在一個(gè)匹配，存在一個(gè)匹配M M，使得使得X X的所有頂點(diǎn)關(guān)于的所有頂點(diǎn)關(guān)于M M飽和的充要條件是：飽和的充要條件是：對于對于X X的任意一個(gè)子集的任意一個(gè)子集A A，和，和A A鄰接的點(diǎn)集為鄰接的點(diǎn)集為T(A)T(A)，恒有：，恒有： |T(A)| = |A| |T(A)| = |A| 11特制分析圖示（圖示（1 1）：）：男1男2女1女

4、2女3返回12特制分析圖示（圖示（2 2）：）：男1男2女1女2女3返回X0=男2V1=男2V2 = T(V1)=女1Y=女1V1=男2，男1V2 =女1Y=女2MM E(P)( 其中，P是從x0 y的可增廣道路 )13特制分析匈牙利算法匈牙利算法基本步驟基本步驟：n1 1任給初始匹配任給初始匹配M M； n2 2若若X X已飽和已飽和則結(jié)束，則結(jié)束，否則否則進(jìn)行第進(jìn)行第3 3步；步； n3 3在在X X中找到一個(gè)非飽和頂點(diǎn)中找到一個(gè)非飽和頂點(diǎn)x0 x0， 作作V1 x0, V2 V1 x0, V2 ； n4 4若若T(V1) = V2T(V1) = V2則因?yàn)闊o法匹配而停止，否則因?yàn)闊o法匹配

5、而停止，否則任選一點(diǎn)則任選一點(diǎn)y T(V1)V2y T(V1)V2； n5 5若若y y已飽和則轉(zhuǎn)已飽和則轉(zhuǎn)6 6，否則做一條從，否則做一條從x0 yx0 y的的可增廣道路可增廣道路P P，MME(P)MME(P)，轉(zhuǎn)，轉(zhuǎn)2 2； n6 6由于由于y y已飽和，所以已飽和，所以M M中有一條邊中有一條邊(y,z)(y,z)，作，作 V1 V1 z, V2 V2 yV1 V1 z, V2 V2 y， 轉(zhuǎn)轉(zhuǎn)4 4； 14特制分析圖示圖示（3 3）：）：男男1男男2女女1女女2返回X0=X0=男男2 2V1=V1=男男22V2 = V2 = T(V1)=T(V1)=女女11T(V1) != V2T(

6、V1) != V2Y=Y=女女1 1V1=V1=男男2 2，男，男11V2 =V2 =女女11T(V1)=V2T(V1)=V215特制分析NOTE:真正求二分圖的最大匹配真正求二分圖的最大匹配的題目很少，往往做一些的題目很少，往往做一些簡單的變化，比如簡單的變化，比如16特制分析變種變種1 1：二分圖的最小頂點(diǎn)覆蓋：二分圖的最小頂點(diǎn)覆蓋在二分圖中求最少的點(diǎn)，讓每條邊都在二分圖中求最少的點(diǎn)，讓每條邊都至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這就是至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這就是二分圖的二分圖的“最小頂點(diǎn)覆蓋最小頂點(diǎn)覆蓋”。17特制分析實(shí)實(shí) 例例 分分 析析18特制分析例例2 2：嚴(yán)禁早戀，違者開除?。簢?yán)禁早戀，違

7、者開除！男生男生女生女生19特制分析例例3 3：HDOJ_1150 HDOJ_1150 任務(wù)安排任務(wù)安排有兩臺機(jī)器有兩臺機(jī)器A A和和B B以及以及N N個(gè)需要運(yùn)行的任務(wù)。每個(gè)需要運(yùn)行的任務(wù)。每臺機(jī)器有臺機(jī)器有M M種不同的模式，而每個(gè)任務(wù)都恰好種不同的模式，而每個(gè)任務(wù)都恰好在一臺機(jī)器上運(yùn)行。如果它在機(jī)器在一臺機(jī)器上運(yùn)行。如果它在機(jī)器A A上運(yùn)行，上運(yùn)行，則機(jī)器則機(jī)器A A需要設(shè)置為模式需要設(shè)置為模式ai,ai,如果它在機(jī)器如果它在機(jī)器B B上上運(yùn)行，則機(jī)器運(yùn)行，則機(jī)器A A需要設(shè)置為模式需要設(shè)置為模式bibi。每臺機(jī)器。每臺機(jī)器上的任務(wù)可以按照任意順序執(zhí)行，但是每臺機(jī)上的任務(wù)可以按照任意順序

8、執(zhí)行，但是每臺機(jī)器每轉(zhuǎn)換一次模式需要重啟一次。請合理為每器每轉(zhuǎn)換一次模式需要重啟一次。請合理為每個(gè)任務(wù)安排一臺機(jī)器并合理安排順序，使得機(jī)個(gè)任務(wù)安排一臺機(jī)器并合理安排順序，使得機(jī)器重啟次數(shù)盡量少。器重啟次數(shù)盡量少。ACM/ICPC Beijing 2002ACM/ICPC Beijing 200220特制分析圖示：圖示：結(jié)論：結(jié)論：二分圖的最小二分圖的最小頂點(diǎn)覆蓋數(shù)頂點(diǎn)覆蓋數(shù) = =二分圖的最大二分圖的最大匹配數(shù)匹配數(shù)a0a1a2a3a4b0b1b2b3b421特制分析特別說明特別說明: :n此題需要注意的一點(diǎn)，具體參見：此題需要注意的一點(diǎn)，具體參見： http:/ 2：DAGDAG圖的最小路徑

9、覆蓋圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖無環(huán)圖(DAG)G(DAG)G的所有頂點(diǎn)，這就是的所有頂點(diǎn)，這就是DAGDAG圖的最小路徑覆蓋問題。圖的最小路徑覆蓋問題。23特制分析例例4：HDOJ_1151 Air RaidHDOJ_1151 Air Raid有一個(gè)城鎮(zhèn)，它的所有街道都是單有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會形成回路。相連。同時(shí)已知街道不會形成回路。你的任務(wù)是編寫程序求最小數(shù)量的你的任務(wù)是編寫程序求最小數(shù)量的傘兵，這些傘兵可以訪問（傘兵，這些傘兵可以訪問（

10、visitvisit）所）所有的路口。對于傘兵的起始降落點(diǎn)不有的路口。對于傘兵的起始降落點(diǎn)不做限制。做限制。24特制分析Input:433 41 32 3Output: 2樣本數(shù)據(jù)：樣本數(shù)據(jù)：25特制分析“空襲空襲”示意圖示意圖12344321132426特制分析結(jié)論：結(jié)論：DAGDAG圖的最小路徑覆蓋數(shù)圖的最小路徑覆蓋數(shù)= =節(jié)點(diǎn)數(shù)（節(jié)點(diǎn)數(shù)（n n）- - 最大匹配數(shù)（最大匹配數(shù)（m m）關(guān)鍵：關(guān)鍵：求二分圖的最大匹配數(shù)求二分圖的最大匹配數(shù)27特制分析變種變種3:3:二分圖的最大獨(dú)立集二分圖的最大獨(dú)立集HDOJ_1068 Girls and BoysHDOJ_1068 Girls and B

11、oys 大學(xué)二年級的時(shí)候，一些同學(xué)開始研究大學(xué)二年級的時(shí)候，一些同學(xué)開始研究男女同學(xué)之間的緣分。研究者試圖找出男女同學(xué)之間的緣分。研究者試圖找出沒有緣分同學(xué)的最大集。程序的結(jié)果就沒有緣分同學(xué)的最大集。程序的結(jié)果就是要輸出這個(gè)集合中學(xué)生的數(shù)量。是要輸出這個(gè)集合中學(xué)生的數(shù)量。28特制分析樣本數(shù)據(jù)：樣本數(shù)據(jù)：輸入：輸入：70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 1輸出：輸出：5 5 29特制分析00154326543216“Girls and Boys”示意圖示意圖30特制分析結(jié)論：結(jié)論：二分圖的最大獨(dú)立集數(shù)二分圖的最

12、大獨(dú)立集數(shù)= =節(jié)點(diǎn)數(shù)（節(jié)點(diǎn)數(shù)（n n） 最大匹配數(shù)（最大匹配數(shù)（m m）關(guān)鍵：關(guān)鍵：求二分圖的最大匹配數(shù)求二分圖的最大匹配數(shù)31特制分析Any Questions?Any Questions?32特制分析相關(guān)練習(xí)n201003201003ACMACM程序程序設(shè)計(jì)設(shè)計(jì)在在線線作作業(yè)業(yè)（1313） 二分匹配二分匹配33特制分析附:參考源碼(HDOJ-1150)/*hdoj_1150匈牙利算法 月下版 */#include#include#includeusing namespace std;bool mark1100,mark2100;int list100;int n,m,edge,num;v

13、ectorvector 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(listpoint=-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,si

14、zeof(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 cout num n)if(n = 0)break;v.clear();v.resize(n);cin m edge;for(i=0;i j s d;vs.push_back(d); Solve(); return 0; 34特制分析Welcome to HDOJWelcome to HDOJThank Thank You You 35特制分析