2366363_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

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

int n, f, d;
int map1[101][101], map2[101][101];
int b[101], link[101];
int B[101], Link[101];

int Find(int v)
{
	int i;

	for(i = 1; i <= d; i++)
	{
		if(map2[v][i]&&!B[i])
		{
			B[i] = 1;
			if(Link[i]==0||Find(Link[i]))
			{
				Link[i] = v;
				return 1;
			}
		}
	}
	return 0;
}

int find(int v)
{
	int i;

	for(i = 1; i <= n; i++)
	{
		if(map1[v][i]&&!b[i])
		{
			b[i] = 1;
			if(link[i]==0)
			{
				memset(B,0,sizeof(B));
				if(Find(i))
				{
					link[i] = v;
					return 1;
				}
			}
			else
				if(find(link[i]))
				{
					link[i] = v;
					return 1;
				}
		}
	}
	return 0;
}

int main()
{
	int i, j, t;
	int fi, di, ans = 0;

	scanf("%d%d%d",&n,&f,&d);
	memset(map1,0,sizeof(map1));
	memset(map2,0,sizeof(map2));
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&fi,&di);
		for(j = 0; j < fi; j++)
		{
			scanf("%d",&t);
			map1[t][i+1] = 1;
		}
		for(j = 0; j < di; j++)
		{
			scanf("%d",&t);
			map2[i+1][t] = 1;
		}
	}
	memset(link,0,sizeof(link));
	memset(Link,0,sizeof(Link));
	for(i = 1; i <= f; i++)
	{
		memset(b,0,sizeof(b));
		if(find(i))
			ans++;
	}
	printf("%d\n",ans);
	return 1;
}