#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 阅读(1316)
评论(1) 编辑 收藏 引用 所属分类:
acm之路