二分圖最大匹配的匈牙利算法：
二分圖是這樣一個(gè)圖，它的頂點(diǎn)可以分類(lèi)兩個(gè)集合X和Y，所有的邊關(guān)聯(lián)在兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合Ｘ，另一個(gè)屬于集合Ｙ。
最大匹配： 圖中包含邊數(shù)最多的匹配稱(chēng)為圖的最大匹配。
完美匹配： 如果所有點(diǎn)都在匹配邊上，稱(chēng)這個(gè)最大匹配是完美匹配。
最小覆蓋： 最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。可以證明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)
最小路徑覆蓋：
用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)圖Ｇ的所有結(jié)點(diǎn)。解決此類(lèi)問(wèn)題可以建立一個(gè)二分圖模型。把所有頂點(diǎn)i拆成兩個(gè)：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m。
二分圖最大匹配的經(jīng)典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根據(jù)一個(gè)初始匹配不停的找增廣路，直到?jīng)]有增廣路為止。
匈牙利算法的本質(zhì)實(shí)際上和基于增廣路特性的最大流算法還是相似的，只需要注意兩點(diǎn)：
（一）每個(gè)X節(jié)點(diǎn)都最多做一次增廣路的起點(diǎn)；
（二）如果一個(gè)Y節(jié)點(diǎn)已經(jīng)匹配了，那么增廣路到這兒的時(shí)候唯一的路徑是走到Y(jié)節(jié)點(diǎn)的匹配點(diǎn)（可以回憶最大流算法中的后向邊，這個(gè)時(shí)候后向邊是可以增流的）。
找增廣路的時(shí)候既可以采用dfs也可以采用bfs，兩者都可以保證O(nm)的復(fù)雜度，因?yàn)槊空乙粭l增廣路的復(fù)雜度是O(m)，而最多增廣n次，dfs在實(shí)際實(shí)現(xiàn)中更加簡(jiǎn)短。
算法思想：
算 法的思路是不停的找增廣軌, 并增加匹配的個(gè)數(shù),增廣軌顧名思義是指一條可以使匹配數(shù)變多的路徑,在匹配問(wèn)題中,增廣軌的表現(xiàn)形式是一條"交錯(cuò)軌",也就 是說(shuō)這條由圖的邊組成的路徑, 它的第一條邊是目前還沒(méi)有參與匹配的,第二條邊參與了匹配,第三條邊沒(méi)有..最后一條邊沒(méi)有參與匹配,并且始點(diǎn)和終點(diǎn)還沒(méi) 有被選擇過(guò).這樣交錯(cuò)進(jìn)行,顯然 他有奇數(shù)條邊.那么對(duì)于這樣一條路徑,我們可以將第一條邊改為已匹配,第二條邊改為未匹配...以此類(lèi)推.也就是將所有 的邊進(jìn)行"反色",容易發(fā)現(xiàn)這樣修 改以后,匹配仍然是合法的,但是匹配數(shù)增加了一對(duì).另外,單獨(dú)的一條連接兩個(gè)未匹配點(diǎn)的邊顯然也是交錯(cuò)軌.可以證明, 當(dāng)不能再找到增廣軌時(shí),就得到了一個(gè) 最大匹配.這也就是匈牙利算法的思路.、
C鄰接矩陣：
#include<stdio.h>
#include<string.h>
#include<math.h>
int result[105];
int state[105];
int data[105][105];
int n1,n2,m,ans;
int init()
{
int i,x,y;
memset(result,0,sizeof(result));
memset(data,0,sizeof(data));
scanf("%d%d%d",&n1,&n2,&m);
for (i=0;i<m ;i++ )
{
scanf("%d%d",&x,&y);
data[x][y]=1;
}
return 0;
}
int find(int x)
{
int i;
for (i=1;i<=n2 ;i++ )
{
if (data[x][i]==1 && !state[i])
{
state[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int i;
init();
ans=0;
for (i=1;i<=n1 ;i++ )
{
memset(state,0,sizeof(state));
if (find(i))
ans++;
}
printf("%d\n",ans);
return 0;
}
POJ_1274:
#include<stdio.h>
#include<string.h>
#include<math.h>
int n,m,ans;
int link[205][205];
int state[205];
int result[205];
int find(int x)
{
int i;
for (i=1;i<=m ;i++ )
{
if (link[x][i] && !state[i])
{
state[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,Si,st;
while (scanf("%d%d",&n,&m)==2)
{
memset(link,0,sizeof(link));
memset(result,0,sizeof(result));
for (i=1;i<=n ;i++ )
{
scanf("%d",&Si);
for (j=1;j<=Si ;j++ )
{
scanf("%d",&st);
link[i][st]=1;
}
}
ans=0;
for (i=1;i<=n ;i++ )
{
memset(state,0,sizeof(state));
if (find(i))
ans++;
}
printf("%d\n",ans);
}
return 0;
}