【HDU - 2063】过山车(二分匹配-匈牙利算法)

题意描述：多实例，每组数据给出男女生可能存在的组合数，然后是女生、男生人数，接下来是每组的女生和男生愿意组队的情况，每个女生只能和她愿意组队的男生一组组队坐过山车，输出可以坐过山车的组合数

解题思路：二分图最大匹配问题，可以利用匈牙利算法，先标记给的组合数据，因为只能1对1，所以先给男孩编号初始化，如果男孩没组队且愿意和女孩一组或者男孩已组队了、尝试把男孩组给女孩，如果组队成功就记录并累加，输出结果。

易错：注意初始化。

#include<bits/stdc++.h>
#define N 1100
using namespace std;
int e[N][N], match[N],book[N];
int k,m,a,b,n;
bool find(int x)//给女孩找组队男孩 
{
	for(int i=1;i<=n;i++)
	{
		if(!book[i]&&e[x][i])
		{
			book[i]=1;
			//如果男孩i还没组队，给女孩x ||男孩已组队、尝试给把男孩i组给女孩x 
			if(!match[i]||find(match[i]))
			{
				match[i]=x;
				return true;
			}
		}	
	}
	return false;//更换不成功、或女孩没组队 
}

int main(void)
{
	while(~scanf("%d",&k))
	{
		if(k==0)
			break;
		scanf("%d %d",&m,&n);
		memset(e,0,sizeof(e));
		memset(match,0,sizeof(match));
		for(int i=1;i<=k;i++)
		{
			scanf("%d %d",&a,&b);
			e[a][b]=1;
		}
		int ans=0;
		for(int i=1;i<=m;i++)//女孩去组队
		{
			memset(book,0,sizeof(book));
			if(find(i))
				ans++;//第i个女孩组队成功，这个配对可能会换，但依然能保证她能配对 
		 } 
		printf("%d\n",ans);
	}
	return 0;
 }