随笔 - 62  文章 - 96  trackbacks - 0
<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

  • 积分 - 231573
  • 排名 - 106

最新评论

阅读排行榜

评论排行榜

#include<cstdio>
#include<memory>
using namespace std;
const int MAX = 10001;
bool map[MAX][MAX],visit[MAX];
int match[MAX];
int a, b;
bool DFS(int i)
{
	int j, k = 1;
	for(j = 1 ; j <= b; j++)
	{
		if(map[i][j] && !visit[j])
		{
			visit[j] = true;
			k = match[j];
			match[j] = i;
			if(k == 0 || DFS(k))
				return true;
			match[j] = k;
		}
	}
	return false;
}
int Hungary()
{	
	int	j, ans = 0;
	memset(match, 0, sizeof(match));
	for(j = 1; j <= a; j++)
	{
		memset(visit,false, sizeof(visit));
		if(DFS(j))
			ans++;
	}
	return ans;
}
int main()
{
	int i, j, n,ans;
	memset(map,false,sizeof(map));
	scanf("%d%d",&a,&b);
	ans = Hungary();
	printf("%d\n",ans);	
	return 0;
}
posted on 2006-10-24 18:34 beyonlin 阅读(1288) 评论(1)  编辑 收藏 引用 所属分类: acm之路

FeedBack:
# re: 最大匹配匈牙利算法 2008-07-07 09:14 Linzertorte
编程风格很好啊。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理