1 题意
题目:luogu P2016: [SEERC 2000] 战略游戏。
在一棵树的节点上放置士兵。一个士兵可以监视与所在节点相连的所有边,求监视全部边所需的最少士兵数。
一条边能被监视,当且仅当至少一个端点放了士兵。因此问题等价于:选择尽量少的节点,使每条边至少有一个端点被选中。 这称为最小顶点覆盖。
注意,要求覆盖的是边。例如链
原题保证
2 父子限制
在 没有上司的舞会 中,一条边的两端不能同时选;本题则是两端不能同时不选。
| 父节点 |
孩子 |
边 |
|---|---|---|
| 不选 | 不选 | 否 |
| 不选 | 选择 | 是 |
| 选择 | 不选 | 是 |
| 选择 | 选择 | 是 |
因此,不选
确定
3 状态定义
任选一个节点为根,记
| 状态 | 含义 |
|---|---|
| 不选 |
|
| 选择 |
状态只要求覆盖子树内部的边,不负责覆盖
这一区分使叶子“不放士兵”的状态也合法:叶子子树内部没有边,需要
4 转移方程
设
4.1 不选 u
若不选
这里不能只要求“至少选一个孩子”。不同孩子对应不同的边,选择一个孩子无法覆盖
4.2 选择 u
选择
选择
4.3 正确性
固定
反过来,各个孩子子树分别取到对应的最优方案,与
5 初值与答案
合并孩子前,初始化为:
叶子没有孩子,这就是它的最终状态。即使叶子上不放士兵,也没有遗漏子树内部的边。
根没有父节点,两个状态都能作为完整方案,答案为:
当
6 手算示例
以下是自拟示例,以
按先孩子、后父亲的顺序计算:
| 节点 |
不选 |
选择 |
|---|---|---|
| 4 | 0 | 1 |
| 5 | 0 | 1 |
| 1 | 2 | 1 |
| 2 | 0 | 1 |
| 3 | 0 | 1 |
| 0 | 3 | 2 |
节点
根的两个状态为:
根已被选中,孩子
示例输入输出
输入:
6
0 3 1 2 3
1 2 4 5
2 0
3 0
4 0
5 0
输出:
2
7 代码实现
洛谷 P2016 的输入先给出 u k 和
输入只描述无向边,不必把每行列出的邻居当作孩子。以 fa 跳过父节点,其余相邻节点就是当前根下的孩子。根的父节点设为
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1500 + 5;
vector<int> g[maxn];
int f[maxn][2];
void dfs(int u, int fa) {
f[u][0] = 0; // 不选 u,先不计入孩子子树的贡献
f[u][1] = 1; // 选 u,先计入 u 上的一名士兵
for (int v : g[u]) {
if (v == fa) continue; // 无向边存了两个方向,跳过父节点
dfs(v, u);
f[u][0] += f[v][1]; // u 不选,必须选 v 来覆盖边 (u,v)
f[u][1] += min(f[v][0], f[v][1]); // u 已覆盖这条边,v 选或不选均可
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int u, k;
cin >> u >> k;
while (k--) {
int v;
cin >> v;
g[u].push_back(v);
g[v].push_back(u); // 输入中每条边只出现一次,这里补齐反向边
}
}
dfs(0, -1); // 无根树可以任选根;节点编号为 0 到 n-1
cout << min(f[0][0], f[0][1]) << '\n';
return 0;
}
每个节点计算两个状态,每条边被扫描两次,时间复杂度为 int 即可。
8 与舞会对照
两题都按子树根选或不选分类,但合法状态来自各自的边约束。
| 比较项 | 没有上司的舞会 | 战略游戏 |
|---|---|---|
| 边的限制 | 两端不能同时选 | 两端不能同时不选 |
| 父节点不选 | 孩子可选或不选 | 孩子必须选 |
| 父节点选择 | 孩子必须不选 | 孩子可选或不选 |
| 优化目标 | 快乐值之和最大 | 选择人数最少 |
状态名称相同,不代表转移相同。先列出一条边两端的合法组合,再写子树转移,才能避免照搬公式。
顶点覆盖与独立集
对于任意图,一个点集是顶点覆盖,当且仅当它的补集是独立集:每条边至少有一端在覆盖集内,等价于没有一条边的两端同时落在补集中。
因此,最小顶点覆盖的大小等于
9 相关题解
暂无相关题解