pku2239.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 60 行

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

int Choose[100];
int st[100][400];
int chk[100];
int N;

int DFS(int p)
{
	int i, t;
	for (i = 0; i < 84; i++)
	{
		if (st[i][p] && !chk[i])
		{
			chk[i] = 1;
			t = Choose[i];
			Choose[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
		}
	}
	return 0;
}

void Solve()
{
	int i;
	int n, p, q;
	int ans;
	memset(st, 0, sizeof(st));
	for (i = 0; i < N; i++)
	{
		scanf("%d", &n);
		while (n--)
		{
			scanf("%d %d", &p, &q);
			st[(p - 1) * 12 + q - 1][i] = 1;
		}
	}
	memset(Choose, -1, sizeof(Choose));
	for (i = 0, ans = 0; i < N; i++)
	{
		memset(chk, 0, sizeof(chk));
		ans += DFS(i);
	}
	printf("%d\n", ans);
}

int main()
{
	while (scanf("%d", &N) != EOF)
	{
		Solve();
	}	
	return 0;
}