二分圖匹配，自然要先從定義入手，那么二分圖是什么呢？
二分圖：
二分圖又稱作二部圖，是圖論中的一種特殊模型。 設(shè)G=(V,E)是一個(gè)無向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集(i in A,j in B)，則稱圖G為一個(gè)二分圖。
簡單的說，一個(gè)圖被分成了兩部分，相同的部分沒有邊，那這個(gè)圖就是二分圖，二分圖是特殊的圖。
匹配：
給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。
極大匹配(Maximal Matching)是指在當(dāng)前已完成的匹配下,無法再通過增加未完成匹配的邊的方式來增加匹配的邊數(shù)。最大匹配(maximum matching)是所有極大匹配當(dāng)中邊數(shù)最大的一個(gè)匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題。
如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。
求二分圖匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)
注意匈牙利算法，除了二分圖多重匹配外在二分圖匹配中都可以使用。
注：二分圖匹配中還有一個(gè)hk算法，復(fù)雜度為o（sqrt（n）*e）由于復(fù)雜度降低較低，代碼量飆升而且絕大多數(shù)情況下沒人會(huì)閑的卡個(gè)sqrt的復(fù)雜度。。在此先不講了，有興趣可以自己百度，貌似卡這個(gè)算法的只有hdu2389嘛。
首先我們講解一下匈牙利算法的過程：
匈牙利算法：
匈牙利算法幾乎是二分圖匹配的核心算法，除了二分圖多重匹配外均可使用
匈牙利算法實(shí)際上就是一種網(wǎng)絡(luò)流的思想，其核心就是尋找增廣路。具體操作就是嗯——拉郎配
注：以下轉(zhuǎn)自 http://blog.csdn.net/dark_scope/article/details/8880547
匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。
-------等等，看得頭大？那么請看下面的版本：
通過數(shù)代人的努力，你終于趕上了剩男剩女的大潮，假設(shè)你是一位光榮的新世紀(jì)媒人，在你的手上有N個(gè)剩男，M個(gè)剩女，每個(gè)人都可能對多名異性有好感（-_-||暫時(shí)不考慮特殊的性取向），如果一對男女互有好感，那么你就可以把這一對撮合在一起，現(xiàn)在讓我們無視掉所有的單相思（好憂傷的感覺)，你擁有的大概就是下面這樣一張關(guān)系圖，每一條連線都表示互有好感。
本著救人一命，勝造七級(jí)浮屠的原則，你想要盡可能地撮合更多的情侶，匈牙利算法的工作模式會(huì)教你這樣做：
一、先試著給1號(hào)男生找妹子，發(fā)現(xiàn)第一個(gè)和他相連的1號(hào)女生還名花無主，got it，連上一條藍(lán)線
二、接著給2號(hào)男生找妹子，發(fā)現(xiàn)第一個(gè)和他相連的2號(hào)女生名花無主，got it
三、接下來是3號(hào)男生，很遺憾1號(hào)女生已經(jīng)有主了，怎么辦呢？
我們試著給之前1號(hào)女生匹配的男生（也就是1號(hào)男生）另外分配一個(gè)妹子。
(黃色表示這條邊被臨時(shí)拆掉)
與1號(hào)男生相連的第二個(gè)女生是2號(hào)女生，但是2號(hào)女生也有主了，怎么辦呢？我們再試著給2號(hào)女生的原配重新找個(gè)妹子(注意這個(gè)步驟和上面是一樣的，這是一個(gè)遞歸的過程)
此時(shí)發(fā)現(xiàn)2號(hào)男生還能找到3號(hào)女生，那么之前的問題迎刃而解了，回溯回去
所以第三步最后的結(jié)果就是：
四、 接下來是4號(hào)男生，很遺憾，按照第三步的節(jié)奏我們沒法給4號(hào)男生騰出來一個(gè)妹子，我們實(shí)在是無能為力了……香吉士同學(xué)走好。
這就是匈牙利算法的流程，其中找妹子是個(gè)遞歸的過程，最最關(guān)鍵的字就是“騰”字。
其原則大概是：有機(jī)會(huì)上，沒機(jī)會(huì)創(chuàng)造機(jī)會(huì)也要上。
核心代碼
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //掃描每個(gè)妹子
if (line[x][j]==true && used[j]==false)
//如果有曖昧并且還沒有標(biāo)記過(這里標(biāo)記的意思是這次查找曾試圖改變過該妹子的歸屬問題，但是沒有成功，所以就不用瞎費(fèi)工夫了）
{
used[j]=1;
if (girl[j]==0 || find(girl[j])) {
//名花無主或者能騰出個(gè)位置來，這里使用遞歸
girl[j]=x;
return true;
}
}
}
return false;
}
在主程序我們這樣做：每一步相當(dāng)于我們上面描述的一二三四中的一步。
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); //這個(gè)在每一步中清空
if find(i) all+=1;
}
例題講解
RPG girls今天和大家一起去游樂場玩，終于可以坐上夢寐以求的過山車了?？墒?，過山車的每一排只有兩個(gè)座位，而且還有條不成文的規(guī)矩，就是每個(gè)女生必須找個(gè)個(gè)男生做partner和她同坐。但是，每個(gè)女孩都有各自的想法，舉個(gè)例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或偽酷兒做partner?？紤]到經(jīng)費(fèi)問題，boss劉決定只讓找到partner的人去坐過山車，其他的人，嘿嘿，就站在下面看著吧。聰明的Acmer，你可以幫忙算算最多有多少對組合可以坐上過山車嗎？
Input
輸入數(shù)據(jù)的第一行是三個(gè)整數(shù)K , M , N，分別表示可能的組合數(shù)目，女生的人數(shù)，男生的人數(shù)。0<K<=1000 ,1<=N 和M<=500.接下來的K行，每行有兩個(gè)數(shù)，分別表示女生Ai愿意和男生Bj做partner。最后一個(gè)0結(jié)束輸入。
Output
對于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示可以坐上過山車的最多組合數(shù)。
Sample Input
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0
Sample Output
3
參考代碼
#include<stdio.h>
#include<string.h>
int a[510][510];
int g[510],u[510];
int m,n;
int fun(int x)
{
int i;
for(i=1;i<=n;i++)
{
if(a[x][i]!=0&&u[i]==0)
{
u[i]=1;
if(g[i]==0||fun(g[i])!=0)
{
g[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,k,x,y;
while(scanf("%d",&k),k!=0)
{
scanf("%d%d",&m,&n);
memset(a,0,sizeof(a));
memset(g,0,sizeof(g));
for(i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
a[x][y]=1;
}
j=0;
for(i=1;i<=m;i++)
{
memset(u,0,sizeof(u));
if(fun(i))
j++;
}
printf("%d\n",j);
}
return 0;
}
