1 条题解
-
0
T2 皇宫守卫(guard)题解
题意简述
给定一棵 个点的树,点 放守卫的代价为 。一个守卫能覆盖自己以及与它相邻的所有点。求覆盖所有点的最小总代价。
思路
这是树上的最小权支配集问题。以 号点为根,对每个点 设计三个状态:
- :在 放守卫,覆盖以 为根的子树的最小代价;
- :不在 放守卫,但 被至少一个儿子上的守卫覆盖;
- :不在 放守卫,且 没有被儿子覆盖,等待父亲来覆盖。
转移
设 的儿子集合为 。
状态 : 自己放了守卫,因此每个儿子 无论处于哪种状态都能被 覆盖,取三者最小值:
$$dp_{u,0}=c_u+\sum_{v\in S(u)}\min(dp_{v,0},dp_{v,1},dp_{v,2}).$$状态 : 没有守卫,儿子不能指望 来覆盖,所以儿子只能是状态 或 :
状态 : 没有守卫,但必须至少有一个儿子放了守卫。先假设每个儿子取 ,然后强制某一个儿子从“较优状态”改成状态 ,取增量最小者:
$$dp_{u,1}=\sum_{v\in S(u)}\min(dp_{v,0},dp_{v,1}) +\min_{v\in S(u)}\left(dp_{v,0}-\min(dp_{v,0},dp_{v,1})\right).$$如果 是叶子,则不存在儿子,。
答案
根节点没有父亲,所以不能处于状态 。答案为
正确性证明
对子树大小归纳,证明三个 值分别等于对应状态下的最小代价。
状态 : 有守卫,子树内每个儿子 都被 覆盖,因此 的子树只需自己覆盖自己, 可以取任意合法状态 。各儿子子树互相独立,取和即最优。
状态 : 没有守卫且没有被儿子覆盖,儿子 不能被 覆盖,所以 不能处于状态 (状态 的含义正是等待父亲覆盖)。 只能取 或 ,取较小值;各儿子独立,故转移正确。
状态 : 没有守卫,儿子不能取状态 。先让每个儿子取 ,若其中至少一个儿子已经取了状态 ,则 已被覆盖;否则所有儿子都取了状态 ,需要把某个儿子改成状态 ,额外代价为 ,选最小者即可。因此转移正确。
根节点: 根没有父亲,状态 不合法;状态 都保证根被覆盖。取最小值即为全局最优。
复杂度
每个点只被访问常数次,时间 ,空间 。
参考代码(C++)
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const long long INF = (long long)4e18; int main() { freopen("guard.in", "r", stdin); freopen("guard.out", "w", stdout); int n; if (scanf("%d", &n) != 1) return 0; vector<long long> c(n + 1); for (int i = 1; i <= n; i++) scanf("%lld", &c[i]); vector<vector<int>> g(n + 1); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } // 迭代求先序,再倒序做树形 DP,避免递归爆栈 vector<int> parent(n + 1, 0), order; order.reserve(n); vector<int> st; st.push_back(1); parent[1] = -1; while (!st.empty()) { int u = st.back(); st.pop_back(); order.push_back(u); for (int v : g[u]) { if (v == parent[u]) continue; parent[v] = u; st.push_back(v); } } vector<long long> dp0(n + 1), dp1(n + 1), dp2(n + 1); for (int idx = n - 1; idx >= 0; idx--) { int u = order[idx]; long long sum0 = c[u]; long long sum01 = 0; long long bestDelta = INF; bool hasChild = false; for (int v : g[u]) { if (v == parent[u]) continue; hasChild = true; sum0 += min(dp0[v], min(dp1[v], dp2[v])); long long m = min(dp0[v], dp1[v]); sum01 += m; bestDelta = min(bestDelta, dp0[v] - m); } dp0[u] = sum0; dp2[u] = sum01; dp1[u] = hasChild ? sum01 + bestDelta : INF; } printf("%lld\n", min(dp0[1], dp1[1])); return 0; }易错点
- 叶子节点的 必须是 :叶子没有儿子,不可能被儿子覆盖。如果误设成 ,会导致根节点“凭空被覆盖”。
- 状态 必须强制至少一个儿子放守卫:只取 会允许所有儿子都不放守卫。
- 根节点不能取状态 :根没有父亲,状态 表示等待父亲覆盖,对根不合法。
- 链的深度可达 :递归 DFS 可能爆栈,建议使用迭代写法。
- 答案要用
long long:,,总和可达 。 - 状态 的儿子可以取状态 :因为 有守卫,儿子等待父亲覆盖是合法的;不要漏掉这个转移。
测试点设计
测试点 设计意图 1 样例 1,链长为 ,答案为 2 样例 2,菊花,比较“中心”与“所有叶子” 3 ,答案为 4 ,答案为 5 链长 ,随机代价,检验基本树形 DP 6 个点的菊花,中心代价为 ,答案为 7 个点的菊花,中心代价为 、叶子代价为 ,答案为 8 个点的随机树,随机大代价 9 个点的链,随机大代价,检验迭代 DFS 与长链 10 个点的随机树,所有代价为 ,答案为最小支配集大小 11 个点的完全二叉树,随机大代价 12 “扫帚”形树:长链末端接大量叶子,检验高度数与大深度同时出现
- 1
信息
- ID
- 7
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者