POJ 1466 最大独立集入门

题意：n个学生，给你每个学生浪漫的学生学号(男女之间浪漫)，问你找出一个最大的集合保证集合内的任意两个学生之间没有相互浪漫关系，输出最大集合的人数。

注意：这里的浪漫边是双向的，如果1对2浪漫，那么2对1也浪漫，题意好像没说清楚，但我测了一下，是双向边。

思路：最大独立集和最小点覆盖集是互补的，所以最大独立集 == 总人数n - 最小点覆盖集，

如果题目给你的是二分图那么直接二分匹配一下即可，但这题不是二分图，我们抓住双向边，那么我们进行拆点，

做一次匹配，求出来的匹配数是(左边男生匹配右边女生 + 左边女生匹配右边男生，这两个值是相等的)，所以原图的最大匹配为 “求出来的匹配数/2”。那么代入公式就可以算出答案了。

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#include <map>

using namespace std;

const int maxn = 1005;

vector <int> edge[maxn];

int id;

int pre[maxn];

bool vis[maxn];

bool dfs(int u) {

	for(int i = 0; i <(int) edge[u].size(); i++) {

		int v = edge[u][i];

		if(vis[v]) continue;

		vis[v] = 1;

		if(pre[v] == -1 || dfs(pre[v])) {

			pre[v] = u;

			return 1;

		}

	}

	return 0;

}

int n;

int main() {

	int i;

	while( ~scanf("%d", &n)) {

		for(i = 0; i < n; i++)

			edge[i].clear();

		int x, y, tp;

		for(i = 0; i < n; i++) {

			scanf("%d: (%d)", &x, &tp);

			while(tp--) {

				scanf("%d", &y);

				edge[x].push_back(y);

			}

		}

		memset(pre, -1, sizeof(int)*n);

		int cnt = 0;

		for(i = 0; i < n; i++) {

			memset(vis, 0, sizeof(bool)*n);

			if(dfs(i)) cnt++;

		}

		printf("%d\n", n-(cnt>>1));

	}

	return 0;

}

巴特西

POJ 1466 最大独立集入门

最新文章

热门文章