pku1466.cpp

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

#include <stdio.h>
#define SIZE 510

typedef struct 
{
	int id;
	int next;
} Node;

int N;
Node nd[250000];
int chk[SIZE];
int match[SIZE];
int End;

int DFS(int p)
{
	int i, t;
	int hd = nd[p].next;
	while (hd != -1)
	{
		i = nd[hd].id;
		if (!chk[i])
		{
			chk[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[i] = t;
		}
		hd = nd[hd].next;
	}
	return 0;
}

void Insert(int hd, int id)
{
	nd[End].id = id;
	nd[End].next = -1;
	while (nd[hd].next != -1)
	{
		hd = nd[hd].next;
	}
	nd[hd].next = End;
	End++;
}

int main()
{
	int i, j, n, one, other;
	int ans;
	while (scanf("%d", &N) != -1 && N > 0)
	{
		memset(nd, -1, sizeof(nd));
		End = 600;
		for (i = 0; i < N; i++)
		{
			scanf("%d: (%d)", &one, &n);
			for (j = 0; j < n; j++)
			{
				scanf("%d", &other);
				Insert(i, other);
			}
		}
		ans = 0;
		memset(match, -1, sizeof(match));
		for (i = 0; i < N; i++)
		{
			memset(chk, 0, sizeof(chk));
			ans += DFS(i);
		}
		printf("%d\n", N - ans / 2);
	}
	return 0;
}