首页 > 代码库 > 最大独立集 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;}
最大独立集 HDU 1068
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。