說說二分圖,其實(shí)圖論的題難點(diǎn)不在用算法,難在如何建圖,只有圖建好了,剩下的就簡單了,在這說說求二分圖的算法,即匈牙利算法,其實(shí)一點(diǎn)都不難,也很好理解拿筆寫寫就行了.
二分圖最大匹配----匈牙利算法
重要的一點(diǎn)就是看出來了用二分圖做,然后就是建圖了,再然后適當(dāng)修改Find函數(shù)就行了.
int n,m;
int link[1001];
bool vis[1001];
vector<int>data[1001];
bool Find(int x)
{
for(int i=0;i<data[x].size();i++){
int m=data[x][i];
if(!vis[m]){
vis[m] = true;
if(!link[m] || Find(link[m])){
link[m] = x;
link[x] = m;
return true;
}
}
}
return false;
}
模板題
AC代碼:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define CLR(x) memset(x,0,sizeof(x))
int n,m;
int link[1001];
bool vis[1001];
vector<int>data[1001];
bool Find(int x)
{
for(int i=0;i<data[x].size();i++){
int m=data[x][i];
if(!vis[m]){
vis[m] = true;
if(!link[m] || Find(link[m])){
link[m] = x;
link[x] = m;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
CLR(link);
int ans=0;
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
data[u].push_back(v);
data[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
CLR(vis);
if(!link[i] && Find(i)) //記住判斷的先后邏輯順序!!!
ans++;
}
printf("%d\n", ans);
}
這里有些重要的定理,有許多題經(jīng)過建圖后發(fā)現(xiàn)就是求這些,故常常配合著這個二分圖來運(yùn)算需要記住!!!
(通過一些小的改變即可達(dá)到要求)
定理：
定理1：最大匹配數(shù)M = 最小點(diǎn)覆蓋數(shù)
定理2：最大獨(dú)立集 = 頂點(diǎn)數(shù) - 最大匹配數(shù)
定理3：有向圖最小路徑覆蓋數(shù) = 頂點(diǎn)數(shù) - 最大匹配數(shù)
定理4：無向圖最小路徑覆蓋數(shù) = 頂點(diǎn)數(shù) - 最大匹配數(shù)/2
（因?yàn)樘幚磉^兩次）
對以上名詞的一些解釋:
最大匹配數(shù)：最大匹配的匹配邊的數(shù)目
最小點(diǎn)覆蓋數(shù)：選取最少的點(diǎn)饮怯，使任意一條邊至少有一個端點(diǎn)被選擇
最大獨(dú)立集：選取最多的點(diǎn)丸冕，使任意所選兩點(diǎn)均不相連
最小路徑覆蓋數(shù)：對于一個 DAG (有向無環(huán)圖),選取最少條路徑,使得每個頂點(diǎn)屬于且僅屬于一條路徑。路徑長可以為 0 (即單個點(diǎn)).
證明略.
二分圖判定----染色法
模板題在此
染色法判斷是否是二分圖.
AC代碼:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define CLR(x) memset(x,0,sizeof(x))
const int maxn=1e4+5;
int cas=1;
bool flag;
int n,m;
bool vis[maxn][maxn]; //vis[i][j] 表示 i 到 j 是否相連過.是的話數(shù)組值為1,否則為 0 .
vector<int>ve[maxn];
int color[maxn];
void dfs(int x,int col)
{
if(!flag) return ; //flag=false, 后面就都沒有必要再搜下去了.
if(!color[x]) color[x]=col; //如果該點(diǎn)沒有被染色,就染上.
else if(color[x]!=col){ //如果遇到將要染色的點(diǎn)不等于將要被染的色,則結(jié)束dfs,不是二分圖.
flag=false;
return ;
}
for(int i=0;i<ve[x].size();i++)
{
int next=ve[x][i];
if(!vis[x][next] && !vis[next][x]){
vis[x][next]=1;
dfs(next,3-col);
}
}
}
int main()
{
int t;
cin >> t;
while(t--){
flag=true;
scanf("%d %d",&n,&m);
CLR(color);
CLR(vis);
for(int i=1;i<=n;i++)
ve[i].clear();
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
ve[u].push_back(v);
ve[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(!color[i]) dfs(i,1); //循環(huán)染色. 分別左邊染1,右邊染2 .
}
if(flag) printf("Correct\n");
else
printf("Wrong\n");
}
}
