首页 > 代码库 > [BZOJ 2350] [Poi2011] Party 【Special】
[BZOJ 2350] [Poi2011] Party 【Special】
题目链接： BZOJ - 2350
题目分析
因为存在一个 2/3 n 大小的团，所以不在这个团中的点最多 1/3 n 个。
牺牲一些团内的点，每次让一个团内的点与一个不在团内的点抵消删除，最多牺牲 1/3 n 个团内的点，至少剩余一个 1/3 n 的团。
如果两个点之间没有边，那么至少有一个点在团外，删掉这两个点！
代码
#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 3000 + 5;int n, m, Cnt;bool D[MaxN], Map[MaxN][MaxN];int main() { scanf("%d%d", &n, &m); int a, b; memset(Map, 0, sizeof(Map)); for (int i = 1; i <= m; ++i) { scanf("%d%d", &a, &b); Map[a][b] = Map[b][a] = true; } memset(D, 0, sizeof(D)); for (int i = 1; i <= n; ++i) if (!D[i]) for (int j = 1; j <= n; ++j) if (j != i && !D[j] && !Map[i][j]) { D[i] = D[j] = true; break; } Cnt = 0; for (int i = 1; i <= n; ++i) { if (D[i]) continue; printf("%d", i); if (++Cnt == n / 3) { printf("\n"); break; } else printf(" "); } return 0;}
[BZOJ 2350] [Poi2011] Party 【Special】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。