臨行上海，決定把最近研究過的各種匹配題做個(gè)匯總，原因是這樣既可以鞏固自己對(duì)匹配問題的掌握，又可以借此復(fù)習(xí)一下匹配問題的各種外在表現(xiàn)形式。我認(rèn)為，如果比賽中出到匹配，出題者在問題的算法上大做文章的可能性不大，大多數(shù)出題者一定會(huì)挖空心思來設(shè)計(jì)一個(gè)讓你眼花繚亂的背景，借此來隱藏匹配問題的實(shí)質(zhì)！
二分圖最小覆蓋的Konig定理及其證明
二分圖：
頂點(diǎn)可以分類兩個(gè)集合X和Y，所有的邊關(guān)聯(lián)在兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合Ｘ，另一個(gè)屬于集合Ｙ。
最小覆蓋：
最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。可以證明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)
Konig定理：
二分圖的最小頂點(diǎn)覆蓋數(shù)等于最大匹配數(shù)。
證明：
為主便敘述，假設(shè)G分為左邊X和右邊Y兩個(gè)互不相交的點(diǎn)集。。。。。。
假設(shè)G經(jīng)過匈牙利算法后找到一個(gè)最大匹配M，則可知G中再也找不到一條增廣路徑。
標(biāo)記右邊未匹配邊的頂點(diǎn)，并從右邊未匹配邊的頂點(diǎn)出發(fā)，按照邊：未匹配->匹配->未匹配...，的原則標(biāo)記途中經(jīng)過的頂點(diǎn)，則最后一條經(jīng)過的邊必定為匹配邊。重復(fù)上述過程，直到右邊不再含有未匹配邊的點(diǎn)。
記得到的左邊已標(biāo)記的點(diǎn)和右邊未標(biāo)記的點(diǎn)為S， 以下證明S即為所求的最小頂點(diǎn)集。
1。| S | == M
顯然，左邊標(biāo)記的點(diǎn)全都為匹配邊的頂點(diǎn)，右邊未標(biāo)記的點(diǎn)也為匹配邊的頂點(diǎn)。因此，我們得到的點(diǎn)與匹配邊一一對(duì)應(yīng)。
2。S能覆蓋G中所有的邊。
上途S中點(diǎn)所得到的邊有以下幾種情況：
（1）左右均標(biāo)記；
（2）左右均無標(biāo)記；
（3）左邊標(biāo)記，右邊未標(biāo)記；
若存在一條邊e不屬于S所覆蓋的邊集，則e 左邊未標(biāo)記右邊標(biāo)記。
如果e不屬于匹配邊，那么左端點(diǎn)就可以通過這條邊到達(dá)（從而得到標(biāo)記）；如果e屬于匹配邊，那么右端點(diǎn)不可能是一條路徑的起點(diǎn)，于是它的標(biāo)記只能是從這條邊的左端點(diǎn)過來的左端點(diǎn)就應(yīng)該有標(biāo)記。
3。S是最小的覆蓋。
因?yàn)橐采w這M條匹配邊至少就需要M個(gè)點(diǎn)。
轉(zhuǎn)自:http://yejingx.ycool.com/post.2801156.html#
在一個(gè)ＰＸＰ的有向圖中，路徑覆蓋就是在圖中找一些路經(jīng)，使之覆蓋了圖中的所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián)；（如果把這些路徑中的每條路徑從它的起始點(diǎn)走到它的終點(diǎn)，那么恰好可以經(jīng)過圖中的每個(gè)頂點(diǎn)一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個(gè)弱連通子集．
由上面可以得出：
１.一個(gè)單獨(dú)的頂點(diǎn)是一條路徑；
２．如果存在一路徑p1,p2,......pk，其中p1 為起點(diǎn)，pk為終點(diǎn)，那么在覆蓋圖中，頂點(diǎn)p1,p2,......pk不再與其它的頂點(diǎn)之間存在有向邊．
最小路徑覆蓋就是找出最小的路徑條數(shù)，使之成為Ｐ的一個(gè)路徑覆蓋．
路徑覆蓋與二分圖匹配的關(guān)系：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；
其中最大匹配數(shù)的求法是把Ｐ中的每個(gè)頂點(diǎn)pi分成兩個(gè)頂點(diǎn)pi'與pi''，如果在p中存在一條pi到pj的邊，那么在二分圖Ｐ＇中就有一條連接pi'與pj''的無向邊；這里pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；
對(duì)于公式：最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；可以這么來理解；
如果匹配數(shù)為零，那么Ｐ中不存在有向邊，于是顯然有：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路徑覆蓋數(shù)為｜Ｐ｜；
Ｐ＇中不在于匹配邊時(shí)，路徑覆蓋數(shù)為｜Ｐ｜；
如果在Ｐ＇中增加一條匹配邊pi'－－＞pj''，那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說pi與pj 在一條路徑上，于是路徑覆蓋數(shù)就可以減少一個(gè)；
如此繼續(xù)增加匹配邊，每增加一條，路徑覆蓋數(shù)就減少一條；直到匹配邊不能繼續(xù)增加時(shí)，路徑覆蓋數(shù)也不能再減少了，此時(shí)就有了前面的公式；但是這里只 是說話了每條匹配邊對(duì)應(yīng)于路徑覆蓋中的一條路徑上的一條連接兩個(gè)點(diǎn)之間的有向邊；下面來說明一個(gè)路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的有向邊對(duì)應(yīng)于一條匹配 邊；
與前面類似，對(duì)于路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的每條有向邊pi--->pj，我們可以在匹配圖中對(duì)應(yīng)做一條連接pi'與pj''的邊， 顯然這樣做出來圖的是一個(gè)匹配圖（這一點(diǎn)用反證法很容易證明，如果得到的圖不是一個(gè)匹配圖，那么這個(gè)圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ，那邊從pi出發(fā)的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類似可證）；
至此，就說明了匹配邊與路徑覆蓋圖中連接兩頂點(diǎn)之間邊的一一對(duì)應(yīng)關(guān)系，那么也就說明了前面的公式成立！
轉(zhuǎn)自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html
POJ 1469 COURSES
學(xué)生選課問題，基礎(chǔ)匹配問題。
有p節(jié)課，n個(gè)學(xué)生，每節(jié)課可以由指定的幾個(gè)學(xué)生參加，但是每個(gè)學(xué)生只能參加一節(jié)課。現(xiàn)在問能不能找到一些學(xué)生使得他們：
1.每個(gè)學(xué)生匹配不同的一節(jié)課
2.每節(jié)課匹配一個(gè)學(xué)生。
就是求個(gè)最大匹配，看看匹配數(shù)是不是等于課程數(shù)。如果相等不就滿足要求了么.
POJ 3041 Asteroids
在N*N的平面上有K顆小行星，現(xiàn)在你要摧毀他們，你的每一發(fā)子彈可以摧毀同一行，或者是同一列上的小行星，現(xiàn)在問你最少要多少子彈才能摧毀所有的小行星？
構(gòu)圖：如果在i行j列上有一顆小行星 則graph[i][j]=1,再求最大匹配即可。
這一題用到的結(jié)論是 ：最小頂點(diǎn)覆蓋 = 最大匹配(最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián))
POJ 2771 Guardian of Decency
老師帶學(xué)生出去旅游，但是擔(dān)心學(xué)生會(huì)發(fā)生戀愛關(guān)系，所以帶出去的學(xué)生至少要滿足以下要求之中的一個(gè)：
1.身高相差40cm以上
2.同性
3.喜歡的音樂風(fēng)格不同
4.喜歡的運(yùn)動(dòng)相同
問最多可以帶出去多少學(xué)生？
個(gè)人感覺如果有男有女，就很有可能是二分匹配了。
這道題我們反過來想，如果將所有可能發(fā)生戀愛關(guān)系的男女配對(duì)，那么可以帶出去的人數(shù)應(yīng)該等于這個(gè)二分圖的最大獨(dú)立集。
根據(jù)公式：
最大獨(dú)立集=頂點(diǎn)數(shù)（包括X和Y)-最大匹配求一次匹配即可。
POJ 3020 Antenna Placement
題目的意思大致就是，一個(gè)矩形中，有N個(gè)城市，現(xiàn)在這n個(gè)城市都要覆蓋無線，若放置一個(gè)基站，那么它至多可以覆蓋相鄰的兩個(gè)城市。
問至少放置多少個(gè)基站才能使得所有的城市都覆蓋無線？
構(gòu)圖：行掃描所有城市,編號(hào),如果有城市相鄰就連一條邊，當(dāng)然如果3和4相鄰，首先graph[3][4]=1,當(dāng)掃描到4時(shí)graph[4][3]也連一條邊，最后只需要取一半即可.求最大匹配的一半，這樣可以得到所有2個(gè)相鄰城市被一個(gè)基站覆蓋所需要的基站數(shù)。然后再加上獨(dú)立的那些基站即可。
公式是:
N-最大匹配(代表所有可以和相鄰城市配對(duì)的城市數(shù)）+最大匹配/2=N-最大匹配/2;
POJ 1325 Machine Schedule
兩臺(tái)機(jī)器A,B,A有n個(gè)模式，B有m個(gè)模式，現(xiàn)在有k個(gè)工作，其中每一個(gè)工作可以由A或B中的一個(gè)特定模式來完成，但是切換機(jī)器的模式要重新啟動(dòng)一次，問最少要重啟多少次機(jī)器才能完成所有工作？
A,B兩臺(tái)機(jī)器構(gòu)成一個(gè)二分圖，在之間按照給出的條件連邊。這樣想，每一個(gè)工作其實(shí)是由一條邊來代表的，那么我們只要用最少的頂點(diǎn)來覆蓋所有的邊即可。這就是最小覆蓋。
根據(jù)公式：
最小覆蓋=最大匹配；對(duì)原二分圖做一次最大匹配即可。
對(duì)了，針對(duì)這個(gè)題還有一個(gè)問題，就是起始狀態(tài)下是在mode 0的，如果在這個(gè)模式下工作，是不需要切換mode的，所以只要有工作是在mode 0下（不管是在A還是在B），對(duì)這個(gè)工作就不連邊，默認(rèn)它不占匹配數(shù)！記得當(dāng)時(shí)就是錯(cuò)在這里，轉(zhuǎn)化很重要啊！
POJ 2226 Muddy Fields(*)
這個(gè)題的原型應(yīng)該是Asteroids的變種，剛看了這道題，一眼就看出了是最小覆蓋，看來我理解了最小覆蓋的內(nèi)在含義了。
農(nóng)夫John的養(yǎng)牛場(chǎng)，是一個(gè)R 行C 列的矩形，一場(chǎng)大雨后，養(yǎng)牛場(chǎng)低洼的地方都有了積水。John 的牛都很嬌貴的，他們吃草的時(shí)候，不想把他們的蹄子給弄臟了。為了不讓牛兒們把它們的蹄子弄臟，John 決定把有水的地方鋪上木板。他的木板是寬度為1，長度沒有限制的。
他想用最少數(shù)目的木板把所有有水的低洼處給覆蓋上，前提是木板不能覆蓋草地，但是可以重疊。
Sample:
4 4
*.*.
.***
***.
..*.
把行里面連在一起的坑連起來視為一個(gè)點(diǎn)，即一塊橫木板，編上序號(hào)，Sample則轉(zhuǎn)化為：
1 0 2 0
0 3 3 3
4 4 4 0
0 0 5 0
把這些序號(hào)加入X集合，再按列做一次則為：
1 0 4 0
0 3 4 5
2 3 4 0
0 0 4 0
同樣加入Y集合，一個(gè)坑只能被橫著的或者被豎著的木板蓋住，將原圖的坑的也標(biāo)上不同的序號(hào)，一共九個(gè)坑
1 . 2 .
. 3 4 5
67 8 .
. . 9 .
比如7號(hào)坑可以被橫著的4號(hào)木板和豎著的3號(hào)木板蓋住，把每個(gè)點(diǎn)的對(duì)應(yīng)的橫木板(4)和豎木板(3)中間連一條邊的話,則問題轉(zhuǎn)化為 找盡量少的邊把這些點(diǎn)都蓋住,根據(jù)定理便是求最大匹配數(shù).
POJ 1422 Air Raid 空襲！
典型的最小路徑覆蓋題，城市之間單向相連，無環(huán)！問最少用多少個(gè)傘兵能遍歷這張圖。
根據(jù)定理：最小路徑覆蓋=頂點(diǎn)數(shù)-最大匹配數(shù)
POJ 3216 Repairing Company(*)
題目說的是一個(gè)城市里面有Q個(gè)點(diǎn)，有M項(xiàng)工作，每個(gè)工作有個(gè)工作地點(diǎn)pi,最晚開始時(shí)間ti，和工作需要的時(shí)間di.
從城市中的任意一個(gè)點(diǎn)到另一個(gè)點(diǎn)的直接時(shí)間又一個(gè)矩陣給出。不連通為-1.注意間接聯(lián)通是被允許的。
我再這個(gè)題上哉了2次，汗啊。我總是以為二分圖的頂點(diǎn)時(shí)基于城市中的點(diǎn)的，但實(shí)際上時(shí)基于工作。
這一題首先對(duì)給定的圖做一次floyd，這樣就能求出兩個(gè)點(diǎn)之間最少需要走的時(shí)間。
然后判斷兩個(gè)工作之間是否存在先后關(guān)系
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&work[i].p,&work[i].t,&work[i].d);
}
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
{
if(work[i].t+work[i].d+g[work[i].p][work[j].p]<=work[j].t)
graph[i][j]=1;
}
最后做最小路徑覆蓋即可。注意這里的頂點(diǎn)數(shù)應(yīng)該是工作數(shù)！這一題值得重點(diǎn)注意！！！
printf("%d\n",m-Hungary(m,graph));
POJ 2594 Treasure Exploration(*)
太經(jīng)典了，最小路徑覆蓋之變形！如果題目中有暗示此圖無環(huán)且路徑是單向的話，必然是最小路徑覆蓋無疑！
這個(gè)題的題目意思和那個(gè)傘兵題差不多，但是傘兵走過的路徑是可以交叉的，這樣我們先做一個(gè)傳遞閉包，然后再連邊做最小路徑覆蓋即可。
POJ 1034 The dog task
一個(gè)很明顯的二分匹配，不過和計(jì)算幾何聯(lián)系起來了。這道題目建圖很巧妙.以BOB行走的n-1條有向線段為X，m個(gè)景點(diǎn)為Y，二分匹配。
暫時(shí)總結(jié)到這，對(duì)于匹配問題，我只想說，匹配問題，你真的很"2"！