1 题意
在树的节点上安排保安。选择节点
一个点集若能使每个节点自身被选,或者与某个被选节点相邻,就称为支配集。本题求树上的最小权支配集;若所有费用均为
原题中
在 战略游戏 中要求覆盖每条边;本题要求覆盖每个点。例如链
2 三种状态
前两篇只需区分子树根选或不选。本题中,根不选还要细分:已经被孩子覆盖,还是需要父节点来覆盖。 两者对父节点的要求不同,不能合并。
记
| 状态 | 对父节点的要求 | |
|---|---|---|
| 不选 |
无 | |
| 选择 |
无 | |
| 不选 |
父节点必须选择 |
每个状态保存满足这些条件的最小费用。状态
3 转移方程
设
3.1 选择 u
选择
3.2 等待父亲
要让
3.3 被孩子覆盖
此时
先不管“至少一个”的限制,记:
如果强制孩子
如果原来的最优选择已经包含某个孩子的状态
这个式子只保证至少选一个孩子,允许其他孩子也被选。不能改成“恰好选择一个孩子”。
4 初值与答案
对于叶子
叶子没有孩子,不能被孩子覆盖;自己选择需要支付费用;等待父亲时暂时不花钱。代码用 INF 表示不可行,并将不可行费用的累加截断到 INF,避免连续相加溢出。
根没有父亲,答案只能是:
特别地,只有一个节点时,必须选择它,答案为它的费用。若把根的状态
5 手算示例
下面是自拟示例。节点外标注费用,实心节点表示选择。选择
| 节点 | 被孩子覆盖 |
自己选择 |
等待父亲 |
|---|---|---|---|
| 4 | 1 | 0 | |
| 2 | 1 | 2 | |
| 3 | 3 | 0 | |
| 1 | 4 | 11 |
根不选时,孩子
6 正确性
固定
状态
从叶子向上归纳,每个状态都是其条件下的最小费用。根排除状态
7 代码实现
P2458 每行依次给出 节点编号 费用 孩子数 孩子列表,已明确父子关系。只保存向孩子的边,找到没有父节点的根。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1500 + 5;
const ll INF = 1LL << 60;
vector<int> g[maxn];
int cost[maxn];
bool has_parent[maxn];
ll f[maxn][3];
void dfs(int u) {
f[u][1] = cost[u]; // 选择 u
f[u][2] = 0; // u 未被子树覆盖,等待父亲选择
ll base = 0, extra = INF;
for (int v : g[u]) {
dfs(v);
// u 选择后,可以接纳孩子的全部三种状态。
f[u][1] += min({f[v][0], f[v][1], f[v][2]});
// u 必须尚未被覆盖,因此孩子不能选,也不能等待 u。
f[u][2] = min(INF, f[u][2] + f[v][0]);
ll best = min(f[v][0], f[v][1]);
base += best; // u 不选,孩子必须在自己的子树内得到覆盖
extra = min(extra, f[v][1] - best); // 强制一个孩子选择的最小补差
}
// 没有孩子时,无法通过孩子覆盖 u。
f[u][0] = (extra == INF ? INF : base + extra);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int u, k;
cin >> u >> k;
cost[u] = k;
int children;
cin >> children;
while (children--) {
int v;
cin >> v;
g[u].push_back(v); // P2458 已给出父亲到孩子的方向
has_parent[v] = true;
}
}
int root = 1;
while (has_parent[root]) ++root;
dfs(root);
// 根没有父亲,不能接受等待父亲覆盖的状态 2。
cout << min(f[root][0], f[root][1]) << '\n';
return 0;
}
每个节点只计算三个状态,每条父子边合并一次,时间复杂度为 long long 为不可行标记及累加留出空间。
8 相关题解
暂无相关题解