愛華網(wǎng)問題簡(jiǎn)介
設(shè)G=(V,E）是一個(gè)無向圖。如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集V1,V2之并，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)不同的子集。則稱圖G為二分圖。二分圖也可記為G=(V1,V2,E）。
給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。
選擇這樣的子集中邊數(shù)最大的子集稱為圖的最大匹配問題（maximal matchingproblem)
如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。
算法描述
在介紹匈牙利算法之前還是先提一下幾個(gè)概念，下面M是G的一個(gè)匹配。
M-交錯(cuò)路：p是G的一條通路，如果p中的邊為屬于M中的邊與不屬于M但屬于G中的邊交替出現(xiàn)，則稱p是一條M-交錯(cuò)路。如：路徑（X3,Y2,X1,Y4），（Y1,X2,Y3）。
M-飽和點(diǎn)：對(duì)于v∈V(G），如果v與M中的某條邊關(guān)聯(lián)，則稱v是M-飽和點(diǎn)，否則稱v是非M-飽和點(diǎn)。如X1，X2，Y1，Y2都屬于M-飽和點(diǎn)，而其它點(diǎn)都屬于非M-飽和點(diǎn)。
M-可增廣路：p是一條M-交錯(cuò)路，如果p的起點(diǎn)和終點(diǎn)都是非M-飽和點(diǎn)，則稱p為M-可增廣路。如（X3,Y2,X1,Y4）。（不要和流網(wǎng)絡(luò)中的增廣路徑弄混了）
求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的時(shí)間復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。下面介紹用增廣路求最大匹配的方法（稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出）。
增廣路的定義（也稱增廣軌或交錯(cuò)軌）：
若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬于M的邊和不屬于M的邊（即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣路徑。
由增廣路的定義可以推出下述三個(gè)結(jié)論：
1－P的路徑個(gè)數(shù)必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。
2－將M和P進(jìn)行取反操作可以得到一個(gè)更大的匹配M’。
3－M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。
算法輪廓：
⑴置M為空
?、普页鲆粭l增廣路徑P，通過異或操作獲得更大的匹配M’代替M
⑶重復(fù)⑵操作直到找不出增廣路徑為止
時(shí)間空間復(fù)雜度
時(shí)間復(fù)雜度 鄰接矩陣：最壞為O(n^3） 鄰接表：O(mn)
空間復(fù)雜度 鄰接矩陣：O(n^2） 鄰接表：O(m+n)
格式說明
輸入格式：
第1行3個(gè)整數(shù)，V1,V2的節(jié)點(diǎn)數(shù)目n1,n2,G的邊數(shù)m
第2-m+1行，每行兩個(gè)整數(shù)t1,t2，代表V1中編號(hào)為t1的點(diǎn)和V2中編號(hào)為t2的點(diǎn)之間有邊相連
輸出格式：
1個(gè)整數(shù)ans，代表最大匹配數(shù)
鄰接矩陣-C
#include <stdio.h>
#include <string.h>
int n1,n2,m,ans;
int result[101]; //記錄V2中的點(diǎn)匹配的點(diǎn)的編號(hào)
bool state [101]; //記錄V2中的每個(gè)點(diǎn)是否被搜索過
bool data[101][101];//鄰接矩陣 true代表有邊相連
void init()
{
int t1,t2;
memset(data,0,sizeof(data));
memset(result,0,sizeof(result));
ans = 0;
scanf("%d%d%d",&n1,&n2,&m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d",&t1,&t2）；
data[t1][t2] = true;
}
return;
}
bool find(int a)
{
for (int i = 1; i <= n2; i++)
{
if (data[a][i] == 1 &&!state[i]) //如果節(jié)點(diǎn)i與a相鄰并且未被查找過
{
state[i] = true; //標(biāo)記i為 已查找過
if (result[i] == 0 //如果i未在前一個(gè)匹配M中
|| find(result[i])) //i在匹配M中，但是從與i相鄰的節(jié)點(diǎn)出發(fā)可以有增廣路
{
result[i] = a; //記錄查找成功記錄
return true; //返回查找成功
}
}
}
return false;
}
int main()
{
init();
for (int i = 1; i <= n1; i++)
{
memset(state,0,sizeof(state)); //清空上次搜索時(shí)的標(biāo)記
if (find(i)) ans++; //從節(jié)點(diǎn)i嘗試擴(kuò)展
}
printf("%dn",ans);
return 0;
}
