2288957_ac_703ms_1012k.c

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

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

int n;
int map[501][501];
int link[501], b[501];

int dfs(int v)
{
	int i;

	for(i = 1; i <= map[v][0]; i++)
	{
		if(!b[map[v][i]])
		{
			b[map[v][i]] = 1;
			if(!link[map[v][i]]||dfs(link[map[v][i]]))
			{
				link[map[v][i]] = v;
				return 1;
			}
		}
	}
	return 0;
}

int input()
{
	int n, p;
	int i, t, tmp;
	int ans;

	if(scanf("%d",&n)!=1)
		return 0;
	memset(link,0,sizeof(link));
	memset(map,0,sizeof(map));
	for(i = 1; i <= n; i++)
	{
		scanf("%d: (%d)",&tmp,&t);
		while(t--)
		{
			scanf("%d",&p);
			map[i][++map[i][0]] = p+1;
			map[p+1][++map[p+1][0]] = i;
		}
	}
	ans = 0;
	for(i = 1; i <= n; i++)
	{
		memset(b,0,sizeof(b));
		ans += dfs(i);
	}
	printf("%d\n",n-ans/2);
	return 1;
}

int main()
{
	while(input());
	return 1;
}