*P3557 [POI2013]GRA-Tower Defense Game

POI 合集。

挺有意思的一道题目。考虑枚举每个点，如果没有被覆盖，那就直接在这个地方建座塔，然后把所有覆盖到的点删掉。正确性是因为存在大小小于 $k$ 的点覆盖集，因此每个点至少与一个点覆盖集中的点相连，在每个点建塔都能覆盖到与所有与该点相连的点覆盖集中的点所能覆盖的点，故贪心正确。

同时，一个点最多仅会作为一次与某座塔距离为 $1$ 的点（因为在此之后所有相邻点都被打上了标记，自然不会再作为塔），遍历其所有出边打标记。故时间复杂度线性。

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0; char s = getchar();
	while(!isdigit(s)) s = getchar();
	while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
	return x;
}

const int N = 1e6 + 5;
int n, m, k, ans, id[N], vis[N], cnt, hd[N], nxt[N << 1], to[N << 1];
void add(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;}
int main() {
	cin >> n >> m >> k;
	for(int i = 1, u, v; i <= m; i++) add(u = read(), v = read()), add(v, u);
	for(int i = 1; i <= n; i++) if(!vis[i]) {
		id[++ans] = i, vis[i] = 1;
		for(int j = hd[i]; j; j = nxt[j]) {
			vis[to[j]] = 1;
			for(int k = hd[to[j]]; k; k = nxt[k]) vis[to[k]] = 1;
		}
	} cout << ans << endl;
	for(int i = 1; i <= ans; i++) cout << id[i] << " ";
	return 0;
}