[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;
}

  

上一篇:someday团队Postmortem(事后诸葛亮会议)


下一篇:GreenDao与ReactiveX的完美搭配