二分圖定義：
頂點集V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬于這兩個互不相交的子集钞诡，兩個子集內(nèi)的頂點不相鄰郑现。同一個子集中沒有兩個點直接相連。
圖中沒有含奇數(shù)條邊的環(huán)荧降。任何無回路的的圖均是二分圖接箫。
二分圖的判定：
如圖一個二分圖FIG.1都可以分成兩個互不相交的子集如圖FIG.2的形式
假如給的圖是連通圖就從1開始染色。如果是非連通圖只要把每個連通塊遍歷一遍就可以了朵诫。
- 如果節(jié)點沒有染過色辛友，就染上與它相反的顏色，推入隊列剪返。
- 如果節(jié)點染過色且相反废累，忽視掉。
- 如果節(jié)點染過色且與父節(jié)點相同脱盲，證明不是二分圖邑滨，return。
二分圖判定：
BFS判定：
bool bfs(int x) { queue<int>qu; color[x]=1; qu.push(x); while(!qu.empty( )) { int k=qu.front( ); qu.pop( ); for(int i=0;i<vep[k].size( );i++) { int v=vep[k][i]; if(color[v]==0) { color[v]=-color[k]; qu.push(v); } else if(color[v]==color[k]) { return false; } } } return true; }DFS判定：
flag=1; void bfs(int x,int k) { color[x]=k; for(int i=0;i<vep[x].size( );i++) { int v=vep[x][i]; if(color[v]==-0) { bfs(v,-k); } else if(color[x]==color[v]) { flag=0; return ; } } }
二分圖最大匹配
給定一個二分圖G钱反，在G的一個子圖M中掖看，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配面哥。(一條邊的兩個端點都不是另外一條邊的端點）
個人覺得很好理解：
注：以下轉(zhuǎn)自 https://blog.csdn.net/dark_scope/article/details/8880547匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出哎壳，因而得名。匈牙利算法是基>于Hall定理中充分性證明的思想尚卫，它是部圖匹配最常見的算法归榕，該算法的核心就:
尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法焕毫。-------等等，看得頭大驶乾？那么請看下面的版本：
通過數(shù)代人的努力邑飒，你終于趕上了剩男剩女的大潮，假設(shè)你是一位光榮的新世紀(jì)媒>人级乐，在你的手上有N個剩男疙咸，M個剩女，每個人都可能對多名異性有好感
-_-||暫時不考慮特殊的性取向）风科，如果一對男女互有好感撒轮，那么你就可以把這一對撮合在一起乞旦，現(xiàn)在讓我們無視掉所有的單相思，你擁有的大概就是下面這樣一張關(guān)系圖题山，每一條連線都表示互有好感兰粉。本著救人一命，勝造七級浮屠的原則顶瞳，你想要盡可能地撮合更多的情侶玖姑，匈牙利算法>的工作模式會教你這樣做：
==============================================================>=================
- 先試著給1號男生找妹子，發(fā)現(xiàn)第一個和他相連的1號女生還名花無主慨菱，got it焰络，連上一條藍(lán)線
==============================================================>=================
- 接著給2號男生找妹子，發(fā)現(xiàn)第一個和他相連的2號女生名花無主符喝，got it
==============================================================>=================
- 接下來是3號男生闪彼，很遺憾1號女生已經(jīng)有主了，怎么辦呢协饲？
我們試著給之前1號女生匹配的男生（也就是1號男生）另外分配一個妹子畏腕。
(黃色表示這條邊被臨時拆掉)
與1號男生相連的第二個女生是2號女生，但是2號女生也有主了囱稽，怎么辦呢郊尝？我們再試著給2號女生的原配重新找個妹子(注意這個步驟和上面是一樣的，這是一個遞歸的過程)
此時發(fā)現(xiàn)2號男生還能找到3號女生战惊，那么之前的問題迎刃而解了流昏，回溯回去
2號男生可以找3號妹子~~~ 1號男生可以找2號妹子了~~~ 3號男生可以找1號妹子
所以第三步最后的結(jié)果就是：
===============================================================================
- 接下來是4號男生，很遺憾吞获，按照第三步的節(jié)奏我們沒法給4號男生騰出來一個妹子况凉，我們實在是無能為力了……香吉士同學(xué)走好。
============================================================
==================
匈牙利算法：
#include<bits/stdc++.h>
using namespace std;
int edge[505][505];
int vis[505];
int L[505];
int k,m,n,x,y;
int Hungarian(int x)
{
for(int i=1;i<=m;i++)
{
if(!vis[i]&&edge[x][i])
//如果有曖昧并且還沒有標(biāo)記過(這里標(biāo)記的意思是這次查找曾試圖改變過該妹子的歸屬問題各拷，但是沒有成功刁绒，所以就不用瞎費工夫了）
{
vis[i]=1;
if(L[i]==-1||Hungarian(L[i]))//名花無主或者能騰出個位置來，這里使用遞歸
{
L[i]=x;
return 1;
}
}
}
return 0;
}
int main( )
{
memset(edge,0,sizeof(edge));
cin>>k>>n>>m;
for(int i=1;i<=k;i++)
{
cin>>x>>y;
edge[x][y]=1;
}
memset(L,-1,sizeof(L));
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));//需要每次更新烤黍；
if(Hungarian(i))
{
ans++;
}
}
cout<<ans<<endl;
return 0;
}
