(HDUACM2010版13)二分匹配及其應(yīng)用學(xué)習(xí)課件

ACM程序設(shè)計(jì)杭州電子科技大學(xué)劉春英acm@1222今天，你開(kāi)始了嗎？復(fù)習(xí)23本周雙星（12）：zhanlang24第十三講二分圖及其應(yīng)用

（BipartiteGraph）25主要內(nèi)容什么是二分圖二分圖的最大匹配匈牙利算法二分圖的最小頂點(diǎn)覆蓋DAG圖的最小路徑覆蓋二分圖的最大獨(dú)立集處理技巧26什么是二分圖？如果一個(gè)圖的頂點(diǎn)可以分為兩個(gè)集合X和Y，圖的所有邊一定是有一個(gè)頂點(diǎn)屬于集合X，另一個(gè)頂點(diǎn)屬于集合Y，則稱該圖為“二分圖”（BipartiteGraph）27例1：婚配問(wèn)題男女28二分圖的最大匹配 在二分圖的應(yīng)用中，最常見(jiàn)的就是最大匹配問(wèn)題，很多其他的問(wèn)題都可以通過(guò)轉(zhuǎn)化為匹配問(wèn)題來(lái)解決。29如何求二分圖的最大匹配呢？210經(jīng)典算法：匈牙利算法211匈牙利算法(求二分圖最大匹配)談匈牙利算法自然避不開(kāi)Hall定理Hall定理：對(duì)于二分圖G，存在一個(gè)匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)于X的任意一個(gè)子集A，和A鄰接的點(diǎn)集為T(mén)(A)，恒有：|T(A)|>=|A|

212圖示（1）：男1男2女1女2女3返回213圖示（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的可增廣道路)214匈牙利算法——基本步驟：1．任給初始匹配M；2．若X已飽和則結(jié)束，否則進(jìn)行第3步；3．在X中找到一個(gè)非飽和頂點(diǎn)x0，作V1←{x0},V2←Φ；4．若T(V1)=V2則因?yàn)闊o(wú)法匹配而停止，否則任選一點(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；

215圖示（3）：男1男2女1女2返回X0=男2V1={男2}V2=ΦT(V1)={女1}T(V1)!=V2Y=女1V1={男2，男1}V2={女1}T(V1)=V2216NOTE: 真正求二分圖的最大匹配的題目很少，往往做一些簡(jiǎn)單的變化，比如——217變種1：二分圖的最小頂點(diǎn)覆蓋 在二分圖中求最少的點(diǎn)，讓每條邊都至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這就是

二分圖的“最小頂點(diǎn)覆蓋”。218實(shí)例分析219例2：嚴(yán)禁早戀，違者開(kāi)除！男生女生220例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ù)盡量少。——ACM/ICPCBeijing2002221圖示：結(jié)論：二分圖的最小頂點(diǎn)覆蓋數(shù)=二分圖的最大匹配數(shù)a0a1a2a3a4b0b1b2b3b4222特別說(shuō)明:此題需要注意的一點(diǎn)，具體參見(jiàn)：

/forum/read.php?tid=61&keyword=%B6%FE%B7%D6223變種2：DAG圖的最小路徑覆蓋 用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)圖(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問(wèn)題。224例4：HDOJ_1151AirRaid 有一個(gè)城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個(gè)路口相連。同時(shí)已知街道不會(huì)形成回路。 你的任務(wù)是編寫(xiě)程序求最小數(shù)量的傘兵，這些傘兵可以訪問(wèn)（visit）所有的路口。對(duì)于傘兵的起始降落點(diǎn)不做限制。225Input: 4

3

34

13

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

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

7

0:(3)456

1:(2)46

2:(0)

3:(0)

4:(2)01

5:(1)0

6:(2)01輸出：5

23000’154326’5’4’3’2’1’6“GirlsandBoys”示意圖231結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)（n）—最大匹配數(shù)（m）關(guān)鍵：求二分圖的最大匹配數(shù)232AnyQuestions?233相關(guān)練習(xí)201003《ACM程序設(shè)計(jì)》在線作業(yè)（13）——二分匹配234附:參考源碼(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,s,d;

while(cin>>n)

{

if(