专栏文章

题解：P3557 [POI 2013] GRA-Tower Defense Game

LLionBlaze
P3557题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio9mea0
此快照首次捕获于
2025/12/02 15:37
3 个月前
此快照最后确认于
2025/12/02 15:37
3 个月前
查看原文
给定一个图，选定不多于 kk 个点，使得图中每个点都离某一个选定的点距离不多于 2\bm 2。无需最小化选点数量。
保证可以选定不多于 kk 个点，使得图中每个点都离某一个选定的点距离不多于 1\bm 1。
这是错误做法
既然有了后面的保证，那么就考虑后面那个题怎么做？
省流：NP 完全的，目前没有发现多项式时间做法。实际上如果你找到了多项式复杂度做法，或者证明了不存在，那么快去领图灵奖吧！
好消息，这个问题是一个经典的问题。坏消息：
当然，如果你不相信 AI，那么百度百科：
那么我们就需要使用下面的条件了。大胆贪心！每次选出一个没有满足条件的点，选择这个点！
这对吗？这能过，实现方法后面讲。这真的对吗？
考虑证明。不妨设我们的解的点集为 AA，而条件中的问题的答案为 BB。根据定义，对于任意一个不在 BB 中的，邻居中都至少有一个 BB 中的点。所以，对于每个 BB 中的点，我们都能找到最多一个 AA 中的点与之对应（就是相邻点或者自身，唯一性是因为两个 AA 中的点距离必然至少为 33），所以 ∣A∣≤∣B∣≤k\lvert A\rvert \le \lvert B\rvert \le k。证毕！
实现方法
DFS。从小到大枚举每个点，如果没有被标记过则 dfs（不考虑标记，考虑标记正确性就不对了）将所有与其距离不多于 22 的点标记上并将自身加入答案中。
看起来一个菊花图就能卡掉是吧！实际上菊花图上选任意一个节点都可以完成。你是卡不掉的。
时间复杂度证明就是，每个点最多和被选中的点相邻一次，也就是只会被遍历一次所有邻居，总时间复杂度就是度数之和 O(m)\mathcal O(m)，加上枚举所有点的复杂度 O(n)\mathcal O(n)。
代码&提交记录
Fun fact：代码和 kk 没有关系。
CPP
#include <cstdio>
#include <vector>

using namespace std;

vector<int> web[500005];

bool vis[500005];

void dfs(int u, int d = 0) // d = depth = 深度
{
	vis[u] = true;
	if (d == 2) return;
	for (int v : web[u])
	{
		dfs(v, d + 1);
	}
}

int main()
{
	int n, m;
	scanf("%d%d%*d", &n, &m); // 冷门小技巧：%*d 可以跳过一个数字，%*c %*s 等同理
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		web[x].push_back(y);
		web[y].push_back(x);
	}
	vector<int> ans;
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			ans.push_back(i);
			dfs(i);
		}
	}
	printf("%d\n", ans.size());
	for (int i : ans)
	{
		printf("%d ", i);
	}
	return 0;
}
record。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...