hdu 1150 Machine Schedule (经典二分匹配)

浏览数：30 / 时间：2015年06月20日

//A组n人 B组m人 
//最多有多少人匹配 每人仅仅有匹配一次
# include<stdio.h>
# include<string.h>
# include<algorithm>
using namespace std;
int n,m,k;
int pp[1100][1100],map[1100],vis[1100];
int bfs(int x)//二分匹配模板
{
	for(int i=1;i<=m;i++)//B组中的人来迎合匹配
	{
		if(!vis[i]&&pp[x][i])
		{
			vis[i]=1;
			if(!map[i]||bfs(map[i]))//b中i还没匹配或与之匹配的A组中的数（map[i]）还能找到其它人匹配
			{
				map[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int count,i,a,b,c;
	while(~scanf("%d",&n),n)
	{
		memset(pp,0,sizeof(pp));//是否匹配
		memset(map,0,sizeof(map));
		scanf("%d%d",&m,&k);
		for(i=0;i<k;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
		    pp[b][c]=1;
		}
		count=0;//匹配数
	    for(i=1;i<=n;i++)//A组中的人进行匹配
		{
			memset(vis,0,sizeof(vis));
			if(bfs(i))
				count++;
		}
		printf("%d\n",count);
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。