塔防游戏 Tower Defense Game：题解

题目理解与问题转化

题目核心：在给定的无向图中，选择尽可能少的点（不超过 k 个），使得图中每个点都至少被一个选中的点在其2步邻域内覆盖。

覆盖规则（升级版瞭望塔）：

• 覆盖自身 (u = v)
• 覆盖直接邻居 (u 和 v 有边直接相连)
• 覆盖邻居的邻居 (存在 w 使得 u-w 和 w-v 都有边)

这实际上是在寻找图的 2-步支配集。

算法思路分析

贪心策略

代码采用了一个非常直观的贪心策略：

1. 初始化：所有点都未被覆盖 (vis[i] = false)
2. 遍历所有点：对于每个点 i，如果它还没有被覆盖：
   • 选择它：将 i 加入答案集合
   • 标记覆盖范围：从 i 出发，通过DFS标记所有距离不超过2的点为已覆盖
3. 输出结果：最终选择的点集就是解

为什么这样可行？

• 完备性：每个未被覆盖的点都会被选中，并覆盖其2步内的所有点
• 正确性：由于覆盖范围是2步，选择当前未被覆盖的点能确保覆盖到它自身
• 最优性（在某种意义下）：这是一个贪心近似算法，虽然不一定是最优解，但能保证找到可行解

代码详解

数据结构

const int N = 5e5 + 7, M = 1e6 + 7;
struct edge {
    int to, nxt;
} e[M << 1];  // 邻接表存储图
int head[N];   // 每个点的第一条边
bool vis[N];   // 标记是否被覆盖
int ans[N];    // 存储选择的点
int tot;       // 选择的点数量

关键函数：DFS覆盖

void dfs(int now, int stp) {
    vis[now] = 1;           // 标记当前点为已覆盖
    
    if (stp == 2) return;   // 关键：只覆盖距离不超过2的点
    
    for (int i = head[now]; i; i = e[i].nxt) {
        dfs(e[i].to, stp + 1);  // 递归覆盖邻居
    }
}

DFS的作用：从选中的点出发，标记所有在2步距离内的点为已覆盖。

主算法流程

for (int i = 1; i <= n; i++) {
    if (!vis[i]) {           // 如果点i还未被覆盖
        ans[++tot] = i;      // 选择点i
        dfs(i, 0);           // 标记i的2步邻域为已覆盖
    }
}

算法正确性证明

定理：上述算法能产生一个有效的2-步支配集。

证明：

1. 覆盖完整性：算法遍历所有点，任何未被覆盖的点都会被选中并覆盖其2步邻域
2. 覆盖有效性：DFS确保每个被选中点能覆盖其2步内的所有点
3. 终止性：图是有限的，算法必然终止

复杂度分析

• 时间复杂度：O(n + m)
  • 每个点最多被DFS访问一次（通过vis数组避免重复）
  • 每条边最多被遍历两次（双向边）
• 空间复杂度：O(n + m)
  • 邻接表存储图：O(n + m)
  • 辅助数组：O(n)

样例分析

以题目样例为例：

9 8 3
1-2  2-3  3-4  1-4
3-5  4-6  7-8  8-9

算法执行过程：

1. 选择点1 → 覆盖 {1,2,3,4}
2. 点5未被覆盖 → 选择点5 → 覆盖 {5,3,2,1,4,6}
3. 点7未被覆盖 → 选择点7 → 覆盖 {7,8,9}

最终输出：3\n1 5 7

学习要点

算法设计技巧

1. 贪心选择：总是选择当前未被覆盖的点
2. 覆盖标记：使用vis数组避免重复处理
3. 距离限制：通过DFS的深度参数控制覆盖范围

图论概念

• 支配集：选择的点集使得每个点要么在集合中，要么与集合中点相邻
• k-步支配集：推广到k步距离的支配集
• 图遍历：DFS在覆盖问题中的应用

这个解法简洁高效，很好地体现了贪心算法在图覆盖问题中的应用。