二分圖定義：
頂點集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è)你是一位光榮的新世紀媒>人，在你的手上有N個剩男，M個剩女，每個人都可能對多名異性有好感
-_-||暫時不考慮特殊的性取向），如果一對男女互有好感，那么你就可以把這一對撮合在一起，現(xiàn)在讓我們無視掉所有的單相思，你擁有的大概就是下面這樣一張關(guān)系圖，每一條連線都表示互有好感。本著救人一命，勝造七級浮屠的原則，你想要盡可能地撮合更多的情侶，匈牙利算法>的工作模式會教你這樣做：
==============================================================>=================
- 先試著給1號男生找妹子，發(fā)現(xiàn)第一個和他相連的1號女生還名花無主，got it，連上一條藍線
==============================================================>=================
- 接著給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])
//如果有曖昧并且還沒有標記過(這里標記的意思是這次查找曾試圖改變過該妹子的歸屬問題，但是沒有成功，所以就不用瞎費工夫了）
{
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;
}
