好萌的講解
以下為部分摘取的一些定義
二分圖：簡單來說，如果圖中點可以被分為兩組，并且使得所有邊都跨越組的邊界，則這就是一個二分圖。準確地說：把一個圖的頂點劃分為兩個不相交集 U 和 V ，使得每一條邊都分別連接U 、 V 中的頂點。如果存在這樣的劃分，則此圖為一個二分圖。二分圖的一個等價定義是：不含有「含奇數條邊的環(huán)」的圖。
匹配：在圖論中，一個「匹配」（matching）是一個邊的集合，其中任意兩條邊都沒有公共頂點。例如，圖 3、圖 4 中紅色的邊就是圖 2 的匹配。
我們定義匹配點、匹配邊、未匹配點、非匹配邊，它們的含義非常顯然。例如圖 3 中 1、4、5、7 為匹配點，其他頂點為未匹配點；1-5、4-7為匹配邊，其他邊為非匹配邊。
最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。圖 4 是一個最大匹配，它包含 4 條匹配邊。
完美匹配：如果一個圖的某個匹配中，所有的頂點都是匹配點，那么它就是一個完美匹配。圖 4 是一個完美匹配。顯然，完美匹配一定是最大匹配（完美匹配的任何一個點都已經匹配，添加一條新的匹配邊一定會與已有的匹配邊沖突）。但并非每個圖都存在完美匹配。
完備匹配：在一個二分圖中找到u->v的一個匹配方案，使得U中所有點出現在該匹配中。
匈牙利算法是用來求解二分無權圖的最大匹配算法
HDU - 2063 過山車
題意:
二分圖無權圖的最大匹配
題解：
- 鄰接矩陣的匈牙利算法
#include <cstdio>
#include<string.h>
#include<iterator>
#include<set>
using namespace std;
const int MAXN=510;
int graph[MAXN][MAXN];
int flower[MAXN];
int used[MAXN];
int n,m;
bool DFS(int x)
{
int i;
for(i=1;i<=m;i++)
{
if(graph[x][i]&&!used[i])
{
used[i]=1;
if((flower[i]==0)||(DFS(flower[i])))
{
flower[i]=x;
return true;
}
}
}
return false;
}
int main()
{
int k,a,b;
while(scanf("%d",&k)!=EOF,k)
{
scanf("%d%d",&n,&m);
memset(graph,0,sizeof(graph));
memset(flower,0,sizeof(flower));
set<int> girl;
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
graph[a][b]=1;
girl.insert(a);
}
int sum=0;
for(set<int>::iterator it=girl.begin();it!=girl.end();it++)
{
memset(used,0,sizeof(used));
if(DFS(*it)) sum++;
}
printf("%d\n",sum);
}
return 0;
}
- 鄰接表的匈牙利算法
#include <cstdio>
#include<string.h>
#include<iterator>
#include<vector>
#include<set>
using namespace std;
const int MAXN=510;
vector<int> graph[MAXN];
int flower[MAXN];
int used[MAXN];
int n,m;
bool DFS(int x)
{
for(int i=0;i<graph[x].size();i++)
{
if(used[graph[x][i]]==0)
{
used[graph[x][i]]=1;
if((flower[graph[x][i]]==0)||DFS(flower[graph[x][i]]))
{
flower[graph[x][i]]=x;
return true;
}
}
}
return false;
}
int main()
{
int k,a,b;
while(scanf("%d",&k)!=EOF,k)
{
scanf("%d%d",&n,&m);
memset(graph,0,sizeof(graph));
memset(flower,0,sizeof(flower));
set<int> girl;
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
girl.insert(a);
}
int sum=0;
for(set<int>::iterator it=girl.begin();it!=girl.end();it++)
{
memset(used,0,sizeof(used));
if(DFS(*it)) sum++;
}
printf("%d\n",sum);
}
return 0;
}
- 前向星的匈牙利算法
#include <cstdio>
#include<string.h>
#include<iterator>
#include<vector>
#include<set>
using namespace std;
const int MAXN=510;
const int MAXEDGE=1010;
struct Node
{
int to,next;
};
Node Edge[MAXEDGE];
int head[MAXN];
int cnt;
void addEdge(int u,int v)
{
Edge[cnt].to=v;
Edge[cnt].next=head[u];
head[u]=cnt++;
}
int flower[MAXN];
int used[MAXN];
int n,m;
bool DFS(int x)
{
for(int i=head[x];i!=-1;i=Edge[i].next)
{
if(!used[Edge[i].to])
{
used[Edge[i].to]=1;
if((flower[Edge[i].to]==0)||DFS(flower[Edge[i].to]))
{
flower[Edge[i].to]=x;
return true;
}
}
}
return false;
}
int main()
{
int k,a,b;
while(scanf("%d",&k)!=EOF,k)
{
scanf("%d%d",&n,&m);
memset(flower,0,sizeof(flower));
memset(head,-1,sizeof(head));
cnt=0;
set<int> girl;
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
addEdge(a,b);
girl.insert(a);
}
int sum=0;
for(set<int>::iterator it=girl.begin();it!=girl.end();it++)
{
memset(used,0,sizeof(used));
if(DFS(*it)) sum++;
}
printf("%d\n",sum);
}
return 0;
}
其實二分匹配也可以用最大流來做的
建一個超級源點,連向一邊所有的點 容量為1;
另外一邊點都連向匯點 容量為1;
二分圖的邊容量也為1
然后跑一遍最大流即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1010;
const int MAXE=5010;
const int INF=0x3f3f3f3f;
int head[MAXN],cnt;
struct Node
{
int to,next,val;
Node(){}
Node(int to,int next,int val):to(to),next(next),val(val){}
};
Node edge[MAXE];
void addEdge(int u,int v,int val)
{
edge[cnt]=Node(v,head[u],val);
head[u]=cnt++;
edge[cnt]=Node(u,head[v],0);
head[v]=cnt++;
}
int step[MAXN];
bool BFS(int st,int ed)
{
queue<int> que;
que.push(st);
memset(step,-1,sizeof(step));
step[st]=0;
int u,v;
while(!que.empty())
{
u=que.front();
que.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(step[v]==-1&&edge[i].val>0)
{
step[v]=step[u]+1;
que.push(v);
if(v==ed) return true;
}
}
}
return false;
}
int DFS(int st,int ed,int flow)
{
if(st==ed||flow==0) return flow;
int v,curr=0;
for(int i=head[st];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(step[v]==step[st]+1&&edge[i].val>0)
{
int d=DFS(v,ed,min(flow,edge[i].val));
if(d>0)
{
edge[i].val-=d;
edge[i^1].val+=d;
curr+=d;
flow-=d;
if(flow==0) break;
}
}
}
if(curr==0) step[st]=INF;
return curr;
}
int Dinic(int st,int ed)
{
int flow=0;
while(BFS(st,ed))
{
flow+=DFS(st,ed,INF);
}
return flow;
}
int main()
{
int k,m,n,a,b,st,ed;
while(scanf("%d",&k)!=EOF,k)
{
scanf("%d%d",&m,&n);
memset(head,-1,sizeof(head));
cnt=st=0;
ed=m+n+1;
for(int i=1;i<=m;i++)
{
addEdge(st,i,1);
}
for(int i=1;i<=n;i++)
{
addEdge(m+i,ed,1);
}
for(int i=0;i<k;i++)
{
scanf("%d%d",&a,&b);
addEdge(a,m+b,1);
}
printf("%d\n",Dinic(st,ed));
}
return 0;
}
