学步园

题意：有n个学生，一男一女可能会陷入浪漫之中，现在知道每个人的浪漫关系。求一个最大集，使得集合里的所有人之间没有浪漫关系。
题解：二分图匹配，最大独立集。

#include <iostream>
using namespace std;

#define N 510
bool vis[N];
int match[N], bond[N][N], cnt[N], n;

bool find_path ( int u )
{
	for ( int i = 1; i <= cnt[u]; i++ )
	{
		int v = bond[u][i];
		if ( ! vis[v] )
		{
			vis[v] = true;    
		    if ( !match[v] || find_path(match[v]) )
			{
			    match[v] = u;
			    return true;
			}
		}
	}
	return false;
}

int Hungary ()
{
	int i, ans = 0;
	memset(match,0,sizeof(match));
	for ( i = 1; i <= n; i++ )
	{
		memset(vis,0,sizeof(vis));
		if ( find_path ( i ) )
			ans++;
	}
	return ans;
}

int main()
{
	int num, u, v, i, j;
	while ( scanf("%d",&n) != EOF )
	{
		memset(bond,0,sizeof(bond));
		memset(cnt,0,sizeof(cnt));

		for ( i = 1; i <= n; i++ )
		{
			scanf("%d: (%d)",&u,&num);
			u++;
			for ( j = 1; j <= num; j++ )
			{
				scanf("%d",&v);
				v++;
				bond[u][++cnt[u]] = v;
			}
		}
		printf("%d\n",n-Hungary()/2);
	}
	return 0;
}