题目链接: 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;
}

  

最新文章

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

热门文章

  1. Mybatis 打开连接池和关闭连接池性能对比
  2. GWT(Google Web Tookit) Eclipse Plugin的zip下载地址(同时提供GWT Designer下载地址)
  3. COMPACT 行记录格式
  4. Emoji表情处理
  5. ASP.NET MVC 第四回 向View传值
  6. jQuery注册验证
  7. WPF TextElement内容模型简介(转)
  8. HTML5 文件域+FileReader 分段读取文件并上传(八)-WebSocket
  9. linux 命令学习(4)
  10. 【算法】数组与矩阵问题——找到无序数组中最小的k个数