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

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

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

2、的頂點可以分為兩個集合X X和和Y Y，圖的所有邊一定是有一個頂點屬于集，圖的所有邊一定是有一個頂點屬于集合合X X，另一個頂點屬于集合，另一個頂點屬于集合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，存在一個匹配，存在一個匹配M M，使得使得X X的所有頂點關(guān)于的所有頂點關(guān)于M M飽和的充要條件是：飽和的充要條件是：對于對于X X的任意一個子集的任意一個子集A A，和，和A A鄰接的點集為鄰接的點集為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é)束，否則否則進行第進行第3 3步；步； n3 3在在X X中找到一個非飽和頂點中找到一個非飽和頂點x0 x0， 作作V1 x0, V2 V1 x0, V2 ； n4 4若若T(V1) = V2T(V1) = V2則因為無法匹配而停止，否則因為無法匹配

5、而停止，否則任選一點則任選一點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：二分圖的最小頂點覆蓋：二分圖的最小頂點覆蓋在二分圖中求最少的點，讓每條邊都在二分圖中求最少的點，讓每條邊都至少和其中的一個點關(guān)聯(lián)，這就是至少和其中的一個點關(guān)聯(lián)，這就是二分圖的二分圖的“最小頂點覆蓋最小頂點覆蓋”。17特制分析實實 例例 分分 析析18特制分析例例2 2：嚴禁早戀，違者開除?。簢澜鐟?，違

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

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

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

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

11、oys 大學(xué)二年級的時候，一些同學(xué)開始研究大學(xué)二年級的時候，一些同學(xué)開始研究男女同學(xué)之間的緣分。研究者試圖找出男女同學(xué)之間的緣分。研究者試圖找出沒有緣分同學(xué)的最大集。程序的結(jié)果就沒有緣分同學(xué)的最大集。程序的結(jié)果就是要輸出這個集合中學(xué)生的數(shù)量。是要輸出這個集合中學(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é)論：二分圖的最大獨立集數(shù)二分圖的最

12、大獨立集數(shù)= =節(jié)點數(shù)（節(jié)點數(shù)（n n） 最大匹配數(shù)（最大匹配數(shù)（m m）關(guān)鍵：關(guān)鍵：求二分圖的最大匹配數(shù)求二分圖的最大匹配數(shù)31特制分析Any Questions?Any Questions?32特制分析相關(guān)練習n201003201003ACMACM程序程序設(shè)計設(shè)計在在線線作作業(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特制分析