增广路径——Hungarian算法（C++）

源代码：

#include<cstdio>
#include<cstring>
int i[1001],m,n,x,ans(0);
bool f[1001][1001]={0},h[1001];
bool x1(int t)
{
for (int a=1;a<=n;a++)
if (f[t][a]&&!h[a]) //此男子有好感的女人。
{
h[a]=true; //标记有男子对此女子倾心。
if (i[a]==0||x1(i[a])) //若此女子单身，或其男友可以另寻芳草。
{
i[a]=t;
return true;
}
}
return false;
}
int main()
{
scanf("%d%d",&m,&n);
for (int a=1;a<=m;a++)
do
{
scanf("%d",&x);
f[a][x]=true;
} 
while (x!=0); //输入图的连通状况。
for (int a=1;a<=m;a++)
{
memset(h,false,sizeof(h)); //在为一个丈夫努力匹配妻子之前，需要进行初始化。
if (x1(a))
ans++; //有老婆的男人数目。
}
printf("%d",ans);
return 0;
}

增广路径——Hungarian算法（C++）

原文：http://www.cnblogs.com/koruko/p/5169993.html