將所有點分成兩個集合，使得所有邊只出現(xiàn)在集合之間，就是二分圖文章來源：http://www.zghlxwxcb.cn/news/detail-714599.html
二分圖：一定不含有奇數(shù)個點數(shù)的環(huán)；可能包含長度為偶數(shù)的環(huán)， 不一定是連通圖文章來源地址http://www.zghlxwxcb.cn/news/detail-714599.html
二分圖的最大匹配：
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;//鄰接表
bool st[N];
int match[N];
void add(int a , int b)
{//頭插法
//如圖 如1與2之間要有一條線，讓2的ne為1，再讓h[1]為2的索引。
//這樣h[1]就是1節(jié)點存的最后一個相連的點，如圖就是7節(jié)點。
//而在索引表內(nèi)部，通過頭插法的方式(即每次ne指向上一個點(h存的就是上一個點))，索引表為：7->4->2
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x)
{
//遍歷自己喜歡的女孩
for(int i = h[x] ; i != -1 ;i = ne[i])
{
int j = e[i];
if(!st[j])//如果在這一輪模擬匹配中,這個女孩尚未被預(yù)定
{
st[j] = true;//那x就預(yù)定這個女孩了，這里預(yù)定是防止她男朋友找其他喜歡的女孩時不重復(fù)找這個
//如果女孩j沒有男朋友，或者她原來的男朋友能夠預(yù)定其它喜歡的女孩。配對成功
if(!match[j]||find(match[j]))
{
match[j] = x;
return true;
}
}
}
//自己中意的全部都被預(yù)定了。配對失敗。
return false;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d%d",&n1,&n2,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
int res = 0;
for(int i = 1; i <= n1 ;i ++)
{
//因為每次模擬匹配的預(yù)定情況都是不一樣的所以每輪模擬都要初始化
memset(st,false,sizeof st);
if(find(i)) res++;//找到一條邊，則res++
}
printf("%d\n",res);
}
到了這里，關(guān)于搜索與圖論：匈牙利算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
