树形动态规划解决最小支配集问题-开发者社区

1. 项目概述：SEERC 2000经典算法题解析

这道来自东南欧地区大学生程序设计竞赛（SEERC）的P2016题目，是图论中经典的"战略游戏"问题。题目描述了一个树形结构的军事布防场景：每个哨所必须被至少一名士兵守卫，且相邻节点不能同时无人值守。我们需要计算出覆盖整棵树所需的最少士兵数量。

这个问题本质上考察的是树形结构上的动态规划应用，属于图论中顶点覆盖问题的变种。在实际应用中，类似的算法可以用于网络监控点布置、交通信号灯优化等场景。我曾在多个算法竞赛中遇到过同类问题，也指导过学生用不同方法解决它。

2. 算法核心思路解析

2.1 问题建模与转化

首先我们需要将问题抽象为图论模型。给定一棵无向树T=(V,E)，要求选择顶点集S⊆V满足：

每条边至少有一个端点在S中
|S|最小

这与标准的顶点覆盖问题不同之处在于：

输入保证是树结构（无环连通图）
相邻节点存在约束条件（不能同时不选）

通过分析可以发现，这实际上是求树的最小支配集（Minimum Dominating Set）问题。对于树结构，这类问题通常有O(n)的解法。

2.2 动态规划状态设计

我们采用树形DP来解决这个问题。定义两个状态：

dp[u][0]：u节点不放置士兵时，子树u需要的最少士兵数
dp[u][1]：u节点放置士兵时，子树u需要的最少士兵数

状态转移方程如下：

对于叶子节点u：

dp[u][0] = INF（不可行）
dp[u][1] = 1

对于非叶子节点u：

dp[u][1] = 1 + Σ min(dp[v][0], dp[v][1]) （v是u的子节点）
dp[u][0] = Σ dp[v][1] （因为u不选，所有子节点必须选）

最终结果就是min(dp[root][0], dp[root][1])

2.3 算法正确性证明

这个DP的正确性基于树结构的无后效性：

子问题独立性：每个子树的最优解只依赖于其子节点的最优解
状态完备性：两种状态覆盖了所有可能情况
转移完整性：考虑了父节点与子节点之间的所有约束关系

通过数学归纳法可以证明，对于高度为h的子树，算法能计算出其最小支配集。

3. 详细实现步骤

3.1 数据结构准备

const int MAXN = 1505; vector<int> tree[MAXN]; int dp[MAXN][2]; // 0: not selected, 1: selected

3.2 核心DP实现

void dfs(int u, int parent) { dp[u][0] = 0; dp[u][1] = 1; for (int v : tree[u]) { if (v == parent) continue; dfs(v, u); dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][0], dp[v][1]); } }

3.3 完整解决方案

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 1505; vector<int> tree[MAXN]; int dp[MAXN][2]; void dfs(int u, int parent) { dp[u][0] = 0; dp[u][1] = 1; for (int v : tree[u) { if (v == parent) continue; dfs(v, u); dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][0], dp[v][1]); } } int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int u, cnt; scanf("%d:(%d)", &u, &cnt); while (cnt--) { int v; cin >> v; tree[u].push_back(v); tree[v].push_back(u); } } dfs(0, -1); cout << min(dp[0][0], dp[0][1]) << endl; return 0; }

4. 算法优化与变种

4.1 空间优化技巧

原始实现使用了O(n)的额外空间。实际上可以进一步优化：

后序遍历代替递归：使用栈模拟DFS，避免递归开销
滚动数组：对于大规模数据，可以只保留当前层和上一层的DP值

void iterative_dfs(int root) { stack<pair<int,int>> s; s.push({root, -1}); while (!s.empty()) { auto [u, parent] = s.top(); if (visited[u]) { // Post-processing for (int v : tree[u]) { if (v != parent) { dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][0], dp[v][1]); } } s.pop(); } else { visited[u] = true; dp[u][0] = 0; dp[u][1] = 1; for (int v : tree[u]) { if (v != parent) s.push({v, u}); } } } }