2288891_ac_15ms_380k.c

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

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

int n;
int map[301][301];
int link[301], b[301];
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 m, n, p;
	int i, t;
	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",&t);
		map[i][0] = t;
		while(t--)
		{
			scanf("%d%d",&m,&p);
			map[i][map[i][0]-t] = (m+p)*(m+p+1)/2+m+1;
		}
	}
	ans = 0;
	for(i = 1; i <= n; i++)
	{
		memset(b,0,sizeof(b));
		ans += dfs(i);
	}
	printf("%d\n",ans);
	return 1;
}

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