HDU 1068 Girls and Boys（最大独力集）

HDU 1068 Girls and Boys（最大独立集）

/*
题意：n个同学，一些男女同学会有缘分成为情侣，格式ni:(m) n1 n2 n3表示同学ni有缘与n1,n2,n3成为情侣，求集合中不存在有缘成为情侣的同学的最大同学数。
题解：
独立集：图的顶点集的子集，其中任意两点不相邻
最大独立集 = 顶点数 - 最大匹配数
由于本题是从整个点集搜索，并不是将点集分开成（A）（B)，（1->2）(2->1)对称存在，所以相当于搜索了两遍。因此真正最大匹配数等于最大匹配数/2.
具体我也不明白其中的原理，只是理解。
*/

#include <iostream>
using namespace std;

const int nMax = 500;
int n;
int map[nMax][nMax];
int link[nMax];
int useif[nMax];

bool can(int t)
{
	for(int i = 0; i < n; ++ i)
	{
		if(!useif[i] && map[t][i])
		{
			useif[i] = 1;
			if(link[i] == -1 || can(link[i]))
			{
				link[i] = t;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	//freopen("f://data.in", "r", stdin);
	while(scanf("%d", &n) != EOF)
	{
		memset(map, 0, sizeof(map));
		memset(link, -1, sizeof(link));
		int u, k, v;
		for(int i = 0; i < n; ++ i)
		{
			scanf("%d: (%d)", &u, &k);
			while(k --)
			{
				scanf("%d", &v);
				map[u][v] = 1;
			}
		}
		int num = 0;
		for(int i = 0; i < n; ++ i)
		{
			memset(useif, 0, sizeof(useif));
			if(can(i)) ++ num;
		}
		printf("%d\n", n - num / 2);
	}
	return 0;
}