点击打开HDU题目链接

题意:有n个学生,每个人都有对另外几个人的亲密关系,求一个集合,是的这个集合种任意两个人都没有亲密关系

分析:先用匈牙利算法求出最大匹配,这些匹配中有一半是男一半是女,那么去除所有男生,将剩下的女生和没有被匹配的所有人放在集合里,就是最大的符合条件的集合。

C++代码:

 

#include <bits/stdc++.h>
using namespace std;

const int maxn = 12800;
vector<int> G[maxn];
int from[maxn], tot;
bool use[maxn];
int n, m;

bool match(int u) {
    for(auto v : G[u]) if(!use[v]) {
        use[v] = true;
        if(from[v] == -1 || match(from[v])) {
            from[v] = u;
            return true;
        }
    }
    return false;
}
int hungary() {
    tot = 0;
    memset(from, -1, sizeof(from));
    for(int i = 1; i <= n; ++i) {
        memset(use, 0, sizeof(use));
        if(match(i)) ++tot;
    }
    return tot;
}

int main() {
    while(~scanf("%d", &n)) {
        for(int i = 0; i < maxn; ++i) G[i].clear();
        int from, to;
        for(int i = 0; i < n; ++i) {
            scanf("%d: (%d)", &from, &m);
            while(m--) {
                scanf("%d", &to);
                G[from+1].push_back(to+1);
            }
        }
        printf("%d\n", n - hungary() / 2);
    }
    return 0;
}

欢迎留言