求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。
增廣路的定義(也稱增廣軌或交錯軌)：
若P是圖G中一條連通兩個未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。
由增廣路的定義可以推出下述三個結(jié)論：
1－P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。
2－P經(jīng)過取反操作可以得到一個更大的匹配M’。
3－M為G的最大匹配當(dāng)且僅當(dāng)不存在相對于M的增廣路徑。
用增廣路求最大匹配(稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)
算法輪廓：
(1)置M為空
(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M
(3)重復(fù)(2)操作直到找不出增廣路徑為止

程序清單：
#include<stdio.h>
#include<string.h>

bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];

bool init()
{
? ? ? ? int _x,_y;
? ? ? ? memset(g,0,sizeof(g));
? ? ? ? memset(link,0,sizeof(link));
? ? ? ? ans=0;
? ? ? ? if(scanf("%d%d",&n,&m)==EOF)return false;
? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? ? ? scanf("%d",&_x);
? ? ? ? ? ? ? ? for(int j=0;j<_x;j++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? scanf("%d",&_y);
? ? ? ? ? ? ? ? ? ? ? ? g[i][_y]=true;
? ? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return true;
}

bool find(int a)
{
? ? ? ? for(int i=1;i<=m;i++)
? ? ? ? {
? ? ? ? ? ? ? ? if(g[a][i]==1&&!b[i])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? b[i]=true;
? ? ? ? ? ? ? ? ? ? ? ? if(link[i]==0||find(link[i]))
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? link[i]=a;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
}

int main()
{
? ? ? ? while(init())
? ? ? ? {
? ? ? ? ? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? memset(b,0,sizeof(b));
? ? ? ? ? ? ? ? ? ? ? ? if(find(i))ans++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? printf("%d\n",ans);
? ? ? ? }
}
下面是同宿舍的小小牛寫的，一起貼上吧，呵呵：