首页 > 代码库 > 最大独立集 HDU 1068

最大独立集 HDU 1068

 

题目大意:有n个人,两个人之间有相互的关系,问最大的关系数目。

思路:n-(最大匹配数/2)。因为这里给出的是n个人之间的两两关系

 

技术分享
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha; printf("haha\n");const int maxn = 500 + 5;int myleft[maxn];int T[maxn];bool vis[maxn][maxn];vector<int> G[maxn];int n;bool match(int u){    int len = G[u].size();    for (int i = 0; i < len; i++){        int v = G[u][i];        if (!T[v]){            T[v] = true;            if (myleft[v] == -1 || match(myleft[v])){                myleft[v] = u;                return true;            }        }    }    return false;}int main(){    while (scanf("%d", &n) == 1){        for (int i = 0; i < n; i++){            for (int j = 0; j < n; j++){                vis[i][j] = false;            }            G[i].clear();        }        for (int i = 1; i <= n; i++){            int k, u;            scanf("%d: (%d)", &u, &k);            for (int i = 0; i < k; i++){                int v; scanf("%d", &v);                G[u].push_back(v);                vis[u][v] = true;            }        }        memset(myleft, -1, sizeof(myleft));        int ans = 0;        for (int i = 0; i < n; i++){            memset(T, 0, sizeof(T));            ans += match(i);        }        for (int i = 0; i < n; i++){            printf("left[%d] = %d\n", i, myleft[i]);        }        printf("%d\n", n - ans / 2);    }    return 0;}
View Code

 

最大独立集 HDU 1068