http://acm.hdu.edu.cn/showproblem.php?pid=2063简单的二分图最大匹配问题，
匈牙利算法解决。
#include <iostream>
using namespace std;
bool g[501][501]; //表示x、y两个集合间元素的连通状态
bool visit[501]; //表示y集合中元素是否被访问
int link[501]; //link[j]表示y中j元素当前与x中连通的元素
int m,n,k;
bool find(int i)
{
int j;
for(j=1;j<=n;j++)
{
if(g[i][j] && visit[j]==false)
{
visit[j]=true; //占领当前元素状态，防止递归下去时被再次占用
if(link[j]==0 || find(link[j])) //如果当前元素不与其他元素连通，或者与它连通的元素构成增广路
{
link[j]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,ans;
while(cin>>k,k)
{
cin>>m>>n;
ans=0;
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
while(k--)
{
cin>>i>>j;
g[i][j]=true;
}
for(i=1;i<=m;i++)
{
memset(visit,0,sizeof(visit)); //每次都要清零
if(find(i)) //不会超过m或者n
ans++;
}
cout<<ans<<endl;
}
return 0;
}posted on 2011-09-12 23:41
大大木马 阅读(424)
评论(0) 编辑 收藏 引用