学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2063

简单的二分图匹配

注意：

1.邻接矩阵G必须初始化

2.当搜索时，i如果已经匹配，再寻找增广路时是 dfs（link[ i ]）;

/***************************
# 2013-9-3 7:30:23 
# Time: 15MS   Memory: 484K
# Author: zyh
# Status: Accepted
***************************/ 


#include<stdio.h>
#include<string.h>

int m,n;
bool G[510][510],vis[510];
int link[510];

bool dfs(int x){
	for(int i=1;i<=n;i++){
		if(G[x][i] && !vis[i]){
			vis[i]=1;
			if(link[i]==-1 || dfs(link[i])){
				link[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int k,i,sum,x,y;
	
	while(scanf("%d",&k),k)
	{
		scanf("%d%d",&m,&n);
		memset(link,-1,sizeof(link));
		memset(G,0,sizeof(G));   //！！！每次必须初始化G 
		
		for(i=0;i<k;i++){
			scanf("%d%d",&x,&y);
			G[x][y] = 1;
		}
		for(sum=0,i=1;i<=m;i++){
			
				memset(vis,0,sizeof(vis));
				if(dfs(i)) sum++;
					
		}
		printf("%d\n",sum);
	}
	return 0;
}