BZOJ 3426 Tower Defense Game

发表于 | 更新于

Link

好吧我不刷POI了。。

Solution

我真的没有意识到

突然XYW的男人看到了他的电脑屏幕：我只要用k座塔就可以了。（保证存在仅用k座塔就可以保卫所有城市的情况）

是题目条件 然后想了很久DP种种

然而因为这个条件，每次只要随便选一个没有被覆盖的就行了。。

在原方案中能覆盖这个点的所有塔的攻击范围的并集一定小于等于这个攻击距离为2的塔的攻击范围——commonc

Tips

好吧改刷省选\UR题

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include "lucida"
const int MAXN=500000+11,MAXM=1000000+11;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXM<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
bool covered[MAXN];
void Cover(int pos,int d=2,int from=0) {
	covered[pos]=1;
	if(d)
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=from)
				Cover(e->to,d-1,pos);
}
int main() {
	freopen("input","r",stdin);
	static int Ans[MAXN],ac;
	int n,m,K;is>>n>>m>>K;
	for(int i=1;i<=m;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	for(int i=1;i<=n;++i)
		if(!covered[i]) {
			Ans[++ac]=i;
			Cover(i);
		}
	os<<ac<<'\n';
	for(int i=1;i<=ac;++i)
		os<<Ans[i]<<(i==ac?'\n':' ');
	return 0;
}