二分圖最大匹配。
以下是我的代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(50007);
const int kMaxm(150007);
struct Edge
{
int u,v;
};
int nx,ny,m;
int cnt,first[kMaxn],next[kMaxm];
Edge e[kMaxm];
int cx[kMaxn],cy[kMaxn];
int distx[kMaxn],disty[kMaxn];
int head,tail,q[kMaxn];
int maxmatch;
void Clear()
{
cnt=0;
for(int i=1;i<=nx;i++)
first[i]=-1;
}
void AddEdge(int u,int v)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
next[cnt]=first[u];
first[u]=cnt;
}
bool BFS()
{
bool re(false);
head=tail=0;
for(int i=1;i<=nx;i++)
distx[i]=0;
for(int i=1;i<=ny;i++)
disty[i]=0;
for(int i=1;i<=nx;i++)
if(cx[i]==-1)
q[tail++]=i;
while(head!=tail)
{
int h,t;
for(h=head,t=tail;h!=t;h=(h+1)%kMaxn)
{
int u(q[h]);
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(!disty[v])
{
disty[v]=distx[u]+1;
if(cy[v]==-1)
re=true;
else
{
distx[cy[v]]=disty[v]+1;
q[tail]=cy[v];
tail=(tail+1)%kMaxn;
}
}
}
}
head=t;
}
return re;
}
bool DFS(int u)
{
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(disty[v]==distx[u]+1)
{
disty[v]=0;
if(cy[v]==-1 || DFS(cy[v]))
{
cx[u]=v;
cy[v]=u;
return true;
}
}
}
return false;
}
void HopcroftKarp()
{
maxmatch=0;
for(int i=1;i<=nx;i++)
cx[i]=-1;
for(int i=1;i<=ny;i++)
cy[i]=-1;
while(BFS())
{
for(int i=1;i<=nx;i++)
if(cx[i]==-1 && DFS(i))
maxmatch++;
}
}
int main()
{
while(scanf("%d%d",&nx,&m)==2)
{
ny=nx;
Clear();
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
AddEdge(u,v);
}
HopcroftKarp();
printf("%d\n",maxmatch);
}
}
posted on 2011-08-11 12:03
lee1r 閱讀(269)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論