信息學競賽算法分析與設計課件

信息學競賽

——算法分析與設計1信息學競賽

——算法分析與設計1本節(jié)課程內容二分圖、匹配(bipartitegraph、matching)匈牙利算法Kuhn-Munkras算法2本節(jié)課程內容二分圖、匹配2二分圖的概念二分圖又稱作二部圖，是圖論中的一種特殊模型。設G=(V,{R})是一個無向圖。如頂點集V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。則稱圖G為二分圖。1122334453二分圖的概念二分圖又稱作二部圖，是圖論中的一種特殊模型。11最大匹配給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximalmatchingproblem)如果一個匹配子圖中，圖中的每個頂點都和匹配子圖中某條邊相關聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。4最大匹配給定一個二分圖G，在G的一個子圖M中，M的邊集{E}匈牙利算法求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的復雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。增廣路的定義(也稱增廣軌或交錯軌)：若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。5匈牙利算法求最大匹配的一種顯而易見的算法是：先找出全部匹配，匈牙利算法由增廣路的定義可以推出下述三個結論：1.P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2.P經過取反操作可以得到一個更大的匹配M’。3.M為G的最大匹配當且僅當不存在相對于M的增廣路徑。6匈牙利算法由增廣路的定義可以推出下述三個結論：6匈牙利算法用增廣路求最大匹配(稱作匈牙利算法，匈牙利數(shù)學家Edmonds于1965年提出)算法輪廓：(1)置M為空(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M(3)重復(2)操作直到找不出增廣路徑為止7匈牙利算法用增廣路求最大匹配(稱作匈牙利算法，匈牙利數(shù)學家E任給初始匹配找xV1為非飽和點S={x},T=取yN(s)-T存在一條從x到y(tǒng)的M可增廣路P，M：=MP無法繼續(xù)匹配，停止存在邊{y,u}MS：=S{u}T：=T{y}M飽和V1N(s)=T?YNYNY已經飽和YN停止，M為最大匹配8任給初始匹配找xV1為非飽和點取yN(s)-T存在一條從設G是具有二部劃分(V1,V2)的二分圖.(1)任給初始匹配M;(2)若M飽和V1則結束.否則轉(3);(3)在V1中找一非M飽和點x,置S={x},T=;(4)若N(S)=T,則停止,否則任選一點yN(S)-T;(5)若y為M飽和點轉(6),否則作求一條從x到y(tǒng)的M可增廣路P,置M=MP,轉(2)(6)由于y是M飽和點,故M中有一邊{y,u},置S=S{u},T=T{y},轉(4).匈牙利算法步驟9設G是具有二部劃分(V1,V2)的二分圖.匈牙利算法步驟9匈牙利算法程序清單：#include<stdio.h>

#include<string.h>

boolg[201][201];

intn,m,ans;

boolb[201];

intlink[201];

10匈牙利算法程序清單：10匈牙利算法boolinit()

{

int_x,_y;

memset(g,0,sizeof(g));

memset(link,0,sizeof(link));

ans=0;

if(scanf(“%d%d”,&n,&m)==EOF)returnfalse;

for(inti=1;i<=n;i++)

{scanf(“%d”,&_x);

for(intj=0;j<_x;j++)

{scanf(“%d”,&_y);

g[i][_y]=true;

}

}

returntrue;

}

11匈牙利算法boolinit()

{

int_x,_匈牙利算法boolfind(inta)

{for(inti=1;i<=m;i++)

{if(g[a][i]==1&&!b[i])

{

b[i]=true;

if(link[i]==0||find(link[i]))

{

link[i]=a;

returntrue;

}

}

}

returnfalse;

}

12匈牙利算法boolfind(inta)

{12匈牙利算法intmain(){

while(init())

{

for(inti=1;i<=n;i++)

{

memset(b,0,sizeof(b));

if(find(i))ans++;

}

printf("%d\n",ans);

}}13匈牙利算法13求二部圖G=(X,Y,E)的(匈牙利算法)迭代步驟:從G的任意匹配M開始.①將X中M的所有非飽和點都給以標號0和標記*,轉向②.

M的非飽和點即非M的某條邊的頂點.②若X中所有有標號的點都已去掉了標記*,則M是G的最大匹配.否則任取X中一個既有標號又有標記*的點xi,去掉xi的標記*,轉向③.③找出在G中所有與xi鄰接的點yj,若所有這樣的yj都已有標號,則轉向②,否則轉向④.14求二部圖G=(X,Y,E)的(匈牙利算法)迭代步④對與xi鄰接且尚未給標號的yj都給定標號i.若所有的

yj都是M的飽和點,則轉向⑤,否則逆向返回.即由其中M的任一個非飽和點

yj的標號i找到xi,再由

xi的標號k找到

yk,…,最后由

yt的標號s找到標號為0的xs時結束,獲得M-增廣路xsyt…xiyj,記P={xsyt,…,xiyj

},重新記M為M⊕P,轉向①.

不必理會M-增廣路的定義.

M⊕P=M∪P

\

M∩P,是對稱差.

⑤

將yj在M中與之鄰接的點xk,給以標號j和標記*,轉向②.15④對與xi鄰接且尚未給標號的yj都給定標號i.例求下圖所示二部圖G的最大匹配.

解①取初始匹配M0={x2

y2,x3

y3,x5

y5}(上圖粗線所示).②給X中M0的兩個非飽和點x1,x4都給以標號0和標記*(如下圖所示).16例求下圖所示二部圖G的最大匹配.解①取初始匹②給X中M0的兩個非飽和點x1,x4都給以標號0和標記*(如下圖所示).

②給X中M0的兩個非飽和點x1,x4都給以標號0和標記*(如下圖所示).17②給X中M0的兩個非飽和點x1,x4都給以標號0和標記*③

去掉x1的標記*,將與x1鄰接的兩個點y2,y3都給以標號1.

因為y2,y3都是M0的兩個飽和點,所以將它們在M0中鄰接的兩個點x2,x3都給以相應的標號和標記*(如下圖所示).18③去掉x1的標記*,將與x1鄰接的兩個點y2,④

去掉x2的標記*,將與x2鄰接且尚未給標號的三個點y1,y4,y5都給以標號2(如下圖所示).19④去掉x2的標記*,將與x2鄰接且尚未給標號的三⑤

因為y1是M0的非飽和點,所以順著標號逆向返回依次得到x2,y2,直到x1為0為止.于是得到M0的增廣路x1y2x2y1,記P={x1y2,y2x2,x2y1}.取M1=M0⊕P={x1y2,x2y1,x3

y3,x5

y5},則M1是比M多一邊的匹配(如下圖所示).20⑤因為y1是M0的非飽和點,所以順著標號逆向返回⑥

再給X中M1的非飽和點x4給以標號0和標記*,然后去掉x4的標記*,將與x4鄰接的兩個點y2,y3都給以標號4.因為y2,y3都是M1的兩個飽和點,所以將它們在M1中鄰接的兩個點x1,x3都給以相應的標號和標記*(如下圖所示).21⑥再給X中M1的非飽和點x4給以標號0和標記*,⑦

去掉x1的標記*,因為與x1鄰接的兩個點y2,y3都有標號4,所以去掉x3的標記*.而與x3鄰接的兩個點y2,y3也都有標號4,此時X中所有有標號的點都已去掉了標記*(如下圖所示),因此M1是G的最大匹配.

G不存在飽和X的每個點的匹配,當然也不存在完美匹配.22⑦去掉x1的標記*,因為與x1鄰接的兩個點y2,最佳匹配如果邊上帶權的話，找出權和最大的匹配叫做求最佳匹配。實際模型：某公司有職員x1,x2,…,xn,他們去做工作y1,y2,…,yn,每個職員做各項工作的效益未必一致，需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。數(shù)學模型：G是加權完全二分圖，求總權值最大的完備匹配。23最佳匹配如果邊上帶權的話，找出權和最大的匹配叫做求最佳匹配。KM算法窮舉的效率－n！，需要更加優(yōu)秀的算法。定理：

設M是一個帶權完全二分圖G的一個完備匹配，給每個頂點一個可行頂標(第i個x頂點的可行標用lx[i]表示，第j個y頂點的可行標用ly[j]表示)，如果對所有的邊(i,j)inG,都有l(wèi)x[i]+ly[j]>=w[i,j]成立(w[i,j]表示邊的權)，且對所有的邊(i,j)inM,都有l(wèi)x[i]+ly[j]=w[i,j]成立，則M是圖G的一個最佳匹配。24KM算法窮舉的效率－n！，需要更加優(yōu)秀的算法。24KM算法對于任意的G和M，可行頂標都是存在的：l(x)=maxw(x,y)l(y)=0欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問題是當標號之后的Gl無完備匹配時怎么辦？1957年Kuhn和Munkras給出了一個解決該問題的有效算法，用逐次修改可行頂標l(v)的辦法使對應的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。25KM算法對于任意的G和M，可行頂標都是存在的：25KM算法修改方法如下：先將一個未被匹配的頂點u(uin{x})做一次增廣路，記下哪些結點被訪問那些結點沒有被訪問。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結點被訪問，j結點沒有被訪問。然后調整lx和ly：對于訪問過的x頂點，將它的可行標減去d，對于所有訪問過的y頂點，將它的可行標增加d。修改后的頂標仍是可行頂標，原來的匹配M仍然存在，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。26KM算法修改方法如下：26KM算法上述算法的證明也很容易Kuhn－Munkras算法流程：(1)初始化可行頂標的值(2)用匈牙利算法尋找完備匹配(3)若未找到完備匹配則修改可行頂標的值(4)重復(2)(3)直到找到相等子圖的完備匹配為止27KM算法上述算法的證明也很容易27作業(yè)：1325MachineSchedule2062CardGameCheater2195GoingHome2226MuddyFields28作業(yè)：1325MachineSchedule28附錄：1PlacetheRobots（ZOJ）

2救護傷員（TOJ1148）3打獵4最小路徑覆蓋5一些例子6二部圖相關的定義、定理29附錄：1PlacetheRobots（ZOJ）2例題1

PlacetheRobots（ZOJ1654）問題描述有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機器人只能放在空地上。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機器人，使它們不能互相攻擊。

Wall

Grass

Empty30例題1PlacetheRobots（ZOJ1654）例題1PlacetheRobots（ZOJ）模型一5467832112346578于是，問題轉化為求圖的最大獨立集問題。在問題的原型中，草地，墻這些信息不是我們所關心的，我們關心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：31例題1PlacetheRobots（ZOJ）模型一5例題1PlacetheRobots（ZOJ）模型一5467832112346578在問題的原型中，草地，墻這些信息不是我們所關心的，我們關心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：這是NP問題！32例題1PlacetheRobots（ZOJ）模型一5我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”。顯然，在一個塊之中，最多只能放一個機器人。我們把這些塊編上號。同樣，把豎直方向的塊也編上號。例題1PlacetheRobots（ZOJ）模型二12345123433我們將每一行，每一列被墻隔開，且包含空地的連續(xù)區(qū)域稱作“塊”例題1PlacetheRobots（ZOJ）模型二123451234把每個橫向塊看作X部的點，豎向塊看作Y部的點，若兩個塊有公共的空地，則在它們之間連邊。于是，問題轉化成這樣的一個二部圖：11223344534例題1PlacetheRobots（ZOJ）模型二1由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問題轉化為二部圖的最大匹配問題。例題1PlacetheRobots（ZOJ）模型二12341235411223344535由于每條邊表示一個空地，有沖突的空地之間必有公共頂點，所以問比較前面的兩個模型：模型一過于簡單，沒有給問題的求解帶來任何便利；模型二則充分抓住了問題的內在聯(lián)系，巧妙地建立了二部圖模型。為什么會產生這種截然不同的結果呢？其一是由于對問題分析的角度不同：模型一以空地為點，模型二以空地為邊；其二是由于對原型中要素的選取有差異：模型一對要素的選取不充分，模型二則保留了原型中“棋盤”這個重要的性質。由此可見，對要素的選取，是圖論建模中至關重要的一步。例題1PlacetheRobots（ZOJ）小結36比較前面的兩個模型：模型一過于簡單，沒有給問題的求解帶來任何例題2

救護傷員（TOJ1148）無情的海嘯奪取了無數(shù)人的生命.很多的醫(yī)療隊被派往災區(qū)拯救傷員.就在此時,醫(yī)療隊突然發(fā)現(xiàn)自己帶的藥品已經不夠用了,只剩下了N種。(1<n<=20)，隨著病人病情的發(fā)展，每種藥在每天能獲得的效果是不一樣的。同時，每天病人只能服用一種藥。也就是說，這些藥還夠支持N天。現(xiàn)在，給出你每種藥在每天使用的效果，請你判斷當每種藥都用完后所有藥達到的效果之和最大可以是多少。37例題2救護傷員（TOJ1148）無情的海嘯奪取了無數(shù)人的例題3

打獵獵人要在n*n的格子里打鳥，他可以在某一行中打一槍，這樣此行中的所有鳥都被打掉，也可以在某一列中打，這樣此列中的所有鳥都打掉。問至少打幾槍，才能打光所有的鳥？建圖：二分圖的X部為每一行，Y部為每一列，如果(i,j)有一只鳥，那么連接X部的i與Y部的j。該二分圖的最大匹配數(shù)則是最少要打的槍數(shù)。38例題3打獵獵人要在n*n的格子里打鳥，他可以在某一行中打例題4

最小路徑覆蓋一個不含圈的有向圖G中，G的一個路徑覆蓋是一個其結點不相交的路徑集合P，圖中的每一個結點僅包含于P中的某一條路徑。路徑可以從任意結點開始和結束，且長度也為任意值，包括0。請你求任意一個不含圈的有向圖G的最小路徑覆蓋數(shù)。理清一個關系：最小路徑覆蓋數(shù)＝G的結點數(shù)－最小路徑覆蓋中的邊數(shù)39例題4最小路徑覆蓋一個不含圈的有向圖G中，G的一個路徑覆蓋例題4最小路徑覆蓋試想我們應該使得最小路徑覆蓋中的邊數(shù)盡量多，但是又不能讓兩條邊在同一個頂點相交。拆點：將每一個頂點i拆成兩個頂點Xi和Yi。然后根據(jù)原圖中邊的信息，從X部往Y部引邊。所有邊的方向都是由X部到Y部。40例題4最小路徑覆蓋試想我們應該使得最小路徑覆蓋中的邊數(shù)盡量例題4最小路徑覆蓋因此，所轉化出的二分圖的最大匹配數(shù)則是原圖G中最小路徑覆蓋上的邊數(shù)。因此由最小路徑覆蓋數(shù)＝原圖G的頂點數(shù)－二分圖的最大匹配數(shù)便可以得解。41例題4最小路徑覆蓋因此，所轉化出的二分圖的最大匹配數(shù)則是原例1m項工作準備分給n個人去做，如圖，其中邊（xi,yj)表示xi,可以從事yj

，如果每個人最多從事其中一項，且每項工作只能由一人擔任。問怎樣才能使盡可能多的人安派上任務。y1y2y3y4y5x1x2x3x4x5二分圖，如xj從事了yi就不能從事yk,同時yi也不允許其它人擔任。相當于用一種顏色，例如紅色，對G的邊著色，保證每個結點最多與一條紅色邊相聯(lián)，這種紅色邊的集合記為M它是圖G的一個匹配。計算G中邊數(shù)最多的匹配。42例1m項工作準備分給n個人去做，如圖，其中邊（xi,yj例2二次大站期間，許多盟軍飛行員到英國參加對法西斯的空襲，當時每架飛機需領航員和飛行員各一名。其中有些只能領航，有些只能駕駛，也有人二者均會。加之二人語言要求相通，如果以結點表示人，邊表示二人語言相通并且一人可領航，另一人可駕駛一可得一圖，這是一簡單圖那么最多的編隊方案就是求成過急G的一個最大匹配。43例2二次大站期間，許多盟軍飛行員到英國參加對法西斯的空襲例.有n張紙牌,每張紙牌的正反兩面都寫上1,2,…n的某一個數(shù),證明:如果每個數(shù)字恰好出現(xiàn)兩次,則這些紙牌一定可以這樣攤開,使朝上的面中1,2,…n都出現(xiàn).44例.有n張紙牌,每張紙牌的正反兩面都寫上44例

某工廠生產由6種不同顏色的紗織成的布，由這個工廠生產的雙色布中每一種顏色至少和其它三種顏色搭配。證明可以挑選出三種不同的雙色布，他們含有所有的6種顏色。45例某工廠生產由6種不同顏色的紗織成的布，由這個工廠生產二部圖：一些例子作者-文章(author-literature)演員-電影(actor-film)基因-疾病(gene-disease)藥物-靶標(drug-proteintarget)基礎醫(yī)學和臨床中的數(shù)據(jù)？。。。。。。。。46二部圖：一些例子作者-文章(author-literatu相關定義、定理定理1：簡單圖G為二部圖

G中所有基本回路的長度為偶數(shù)。定義1：設無向圖G＝<V，E>，M

E，若M中任意兩條邊都不相鄰，則稱M為G的一個匹配，并把M中的邊所關聯(lián)的兩個結點稱為在M下是匹配的。若在M中再加入任何一條邊就不是匹配了，稱M為極大匹配。邊數(shù)最多的極大匹配稱為G的最大匹配。最大匹配中的邊的個數(shù)稱為G的匹配數(shù)。

M是G中的一個匹配，若結點v與M中的邊關聯(lián)，稱v為M飽和點，否則稱v為M非飽和點。若G中每個結點都是M飽和點，稱M是完全匹配。47相關定義、定理定理1：簡單圖G為二部圖G中所有基本回路的定義2：設G＝<V1，V2，E>為二部圖，M是G中一個最大匹配，若|M|＝min{|V1|，|V2|}，稱M為G中的一個完備匹配。若此時|V1|

|V2|，稱M為V1到V2的一個完備匹配。若|V1|＝|V2|，稱M為G的完全匹配。定理3(Hall定理)：設G＝<V1，V2，E>，|V1|

|V2|，G中存在從V1到V2的完備匹配

V1中任意k個結點(k＝1，2，…，|V1|)至少鄰接V2中的k個結點。48定義2：設G＝<V1，V2，E>為二部圖，M是G中一個最大定理4(t條件)：設G＝<V1，V2，E>，若V1中每個結點至少關聯(lián)t(t＞0)條邊，而V2中每個結點至多關聯(lián)t條邊，則G中存在V1到V2的完備匹配。推論：G＝<V1，V2，E>，對任意v∈V1或V2有d(v)＝k＞0，則G有一個完全匹配。49定理4(t條件)：設G＝<V1，V2，E>，若V1中每個結例：某大學計算機系有3個課外學習小組：網絡組、網頁制作組和數(shù)據(jù)庫