挑战程序设计竞赛,283页,二分图最大独立集
二分图的最大独立集
题目意思:
在一群男女生之间存在浪漫关系,且只存在于男女之间,现给出存在关系的人的编号,但没给具体的男女性别,
现在要求一个集合,在集合中任意两人都不存浪漫关系,输出集合中元素的个数.
本题要点:
1、定理:
二分图的最大独立集 = 总点数 - 最大匹配数
2、这里采用邻接表来存图。用增广路算法求出最大匹配数。
二分图匹配,因为没有分左右每对匹配会出现两次。 最后算出来的 ans 要除以2;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 510, MaxM = 250010;;
int head[MaxN], ver[MaxM], Next[MaxM], match[MaxN];
int n, tot;
bool vis[MaxN];void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}bool dfs(int x)
{
for(int i = head[x]; i; i = Next[i]){
int y = ver[i];if(!vis[y]){
vis[y] = true;if(!match[y] || dfs(match[y])){
match[y] = x;return true;}}}return false;
}int main()
{
char s[10] = {
0};int k;while(scanf("%d", &n) != EOF){
int j;tot = 0;memset(head, 0, sizeof head);memset(Next, 0, sizeof Next);memset(match, 0, sizeof match);for(int i = 0; i < n; ++i){
scanf("%s", s); scanf("%s", s); s[strlen(s) - 1] = '\0';k = atoi(s + 1);while(k--){
scanf("%d", &j); add(i, j);}}int ans = 0;for(int i = 0; i < n; ++i){
memset(vis, 0, sizeof vis);if(dfs(i))++ans;}printf("%d\n", n - ans / 2);}return 0;
}/* 7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0 *//* 5 2 */