電acm課件二分匹配及其應(yīng)用

ACM程序設(shè)計(jì)杭州電子科技大學(xué)劉春英

2022/10/262今天，你開始了嗎？復(fù)習(xí)2022/10/263本周雙星（11）：07057319李覺小蜜蜂

2022/10/264第十二講二分圖及其應(yīng)用

（BipartiteGraph）2022/10/265主要內(nèi)容什么是二分圖二分圖的最大匹配匈牙利算法二分圖的最小頂點(diǎn)覆蓋DAG圖的最小路徑覆蓋二分圖的最大獨(dú)立集處理技巧2022/10/266什么是二分圖？如果一個(gè)圖的頂點(diǎn)可以分為兩個(gè)集合X和Y，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合X，另一個(gè)頂點(diǎn)屬于集合Y，則稱該圖為“二分圖”（BipartiteGraph）2022/10/267例1：婚配問題男女2022/10/268二分圖的最大匹配

在二分圖的應(yīng)用中，最常見的就是最大匹配問題，很多其他的問題都可以通過轉(zhuǎn)化為匹配問題來解決。2022/10/269如何求二分圖的最大匹配呢？2022/10/2610經(jīng)典算法：匈牙利算法2022/10/2611匈牙利算法(求二分圖最大匹配)談匈牙利算法自然避不開Hall定理Hall定理：對(duì)于二分圖G，存在一個(gè)匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)于X的任意一個(gè)子集A，和A鄰接的點(diǎn)集為T(A)，恒有：|T(A)|>=|A|

2022/10/2612圖示（1）：男1男2女1女2女3返回2022/10/2613圖示（2）：男1男2女1女2女3返回X0=男2V1={男2}V2=ΦT(V1)={女1}Y=女1V1={男2，男1}V2={女1}Y=女2M←M⊕E(P)(其中，P是從x0→y的可增廣道路)2022/10/2614匈牙利算法——基本步驟：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，M←M⊕E(P)，轉(zhuǎn)2；6．由于y已飽和，所以M中有一條邊(y,z)，作V1←V1∪{z},V2←V2∪{y}，轉(zhuǎn)4；

2022/10/2615圖示（3）：男1男2女1女2返回X0=男2V1={男2}V2=ΦT(V1)={女1}T(V1)!=V2Y=女1V1={男2，男1}V2={女1}T(V1)=V22022/10/2616NOTE:

真正求二分圖的最大匹配的題目很少，往往做一些簡(jiǎn)單的變化，比如——2022/10/2617變種1：二分圖的最小頂點(diǎn)覆蓋

在二分圖中求最少的點(diǎn)，讓每條邊都至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這就是

二分圖的“最小頂點(diǎn)覆蓋”。2022/10/2618實(shí)例分析2022/10/2619例2：嚴(yán)禁早戀，違者開除！男生女生2022/10/2620例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ī)器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ù)盡量少?！狝CM/ICPCBeijing20022022/10/2621圖示：結(jié)論：二分圖的最小頂點(diǎn)覆蓋數(shù)=二分圖的最大匹配數(shù)a0a1a2a3a4b0b1b2b3b42022/10/2622特別說明:此題需要注意的一點(diǎn)，具體參見：

2022/10/2623變種2：DAG圖的最小路徑覆蓋

用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無環(huán)圖(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。2022/10/2624例4：HDOJ_1151AirRaid

有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會(huì)形成回路。 你的任務(wù)是編寫程序求最小數(shù)量的傘兵，這些傘兵可以訪問（visit）所有的路口。對(duì)于傘兵的起始降落點(diǎn)不做限制。2022/10/2625Input: 4

3

34

13

23Output:2樣本數(shù)據(jù)：2022/10/2626“空襲”示意圖12344’3’2’1’13242022/10/2627結(jié)論：DAG圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)（n）-最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù)2022/10/2628變種3:二分圖的最大獨(dú)立集HDOJ_1068GirlsandBoys

大學(xué)二年級(jí)的時(shí)候，一些同學(xué)開始研究男女同學(xué)之間的緣分。研究者試圖找出沒有緣分同學(xué)的最大集。程序的結(jié)果就是要輸出這個(gè)集合中學(xué)生的數(shù)量。2022/10/2629樣本數(shù)據(jù)：

輸入：

7

0:(3)456

1:(2)46

2:(0)

3:(0)

4:(2)01

5:(1)0

6:(2)01輸出：5

2022/10/263000’154326’5’4’3’2’1’6“GirlsandBoys”示意圖2022/10/2631結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)（n）—

最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù)2022/10/2632AnyQuestions?2022/10/2633相關(guān)練習(xí)HDOJ_1068(二分圖最大獨(dú)立集=n-m)HDOJ_1150(二分圖最小頂點(diǎn)覆蓋=m)HDOJ_1151(二分圖最小路徑覆蓋=n-m)HDOJ_1281HDOJ_1498HDOJ_1528HDOJ_1507POJ_2724POJ_32162022/10/2634附:參考源碼(HDOJ-1150)/*hdoj_1150匈牙利算法月下版*/

#include<iostream>

#include<string>

#include<vector>

usingnamespacestd;

boolmark1[100],mark2[100];

intlist[100];

intn,m,edge,num;

vector<vector<int>>v;

booldfs(intto)

{

registerinti,point,s=list[to];

for(i=0;i<v[s].size();i++)

{

point=v[s][i];

if(!mark2[point])

continue;

mark2[point]=false;

if(list[point]==-1||dfs(point)){

list[point]=s;

returntrue;

}

}

returnfalse;

}

voidSolve()

{

inti,j,point;

boolflog=false;

memset(mark1,true,sizeof(mark1));

memset(list,-1,sizeof(list));

num=0;

for(i=0;i<n;i++)

{

for(j=0;j<v[i].size();j++)

if(list[v[i][j]]==-1)

{

mark1[i]=false;

list[v[i][j]]=i;

num++;

if(i==0)flog=true;

break;

}

}for(i=0;i<n;i++)

{

if(mark1[i])

{

if(!v[i].empty()){

memset(mark2,true,sizeof(mark2));

for(j=0;j<v[i].size();j++)

{

point=v[i][j];

if(!mark2[point])continue;

mark2[point]=false;

if(list[point]==-1||dfs(point))

{

list[point]=i;

num++;

break;

}

}

}

mark1[i]=false;

}

}

if(flog||list[0]!=-1)

cout<<num-1<<endl;

elsecout<<num<<endl;

}

intmain()

{

inti,j,