[BZOJ 2350] [Poi2011] Party 【Special】
2024-10-15 23:29:14
题目链接: 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;
}
最新文章
- NYOJ题目27水池数目
- java:JDBC详解
- 【POJ 2774】Long Long Message 最长公共子串
- HDU 4320 Arcane Numbers 1 (质因子分解)
- [像黑客一样生活] shell终端听音乐之网易云shell版
- 【poj3348】 Cows
- Error: [$injector:unpr] angular.js
- jira破解
- [转]将某个Qt4项目升级到Qt5遇到的问题
- BAE 环境下配置 struts2 + spring + hibernate(SSH)(三)spring&;hibernate
- WPF - EventSetter
- iOS 改变UITextField中光标颜色
- 注解&#160;@Resource与@Autowired与@Component的使用
- About Undefined Behavior[译文]
- 基于visual Studio2013解决C语言竞赛题之0806平均分
- 阿里云ECSserver部署django
- nginx系列13:最少连接算法以及如何跨worker进程生效
- 我的第一个python web开发框架(25)——定制ORM(一)
- MariaDB导入XXX.sql文件
- position:fixed 失效