Problem
考察算法：树形 \(DP\)。
题目简述
给你一个树，如果树上的某个节点上放置了一个士兵，那么与其相连的所有边上的点都能被瞭望到。
求：最少要放置几个士兵，能使得整个树上每个点都能被瞭望到？
思路
设 二维数组 \(f[x][0/1]\)。
- \(f[x][0]\) 表示不在 \(x\) 点放置士兵而使 \(x\) 节点及其所有子树上的点都能被瞭望到的最小放置士兵数。
- \(f[x][1]\) 表示在 \(x\) 点放置士兵而使 \(x\) 节点及其所有子树上的点都能被瞭望到的最小花费。
最终的答案为：\(\min(f[r][0], f[r][1])\)。\(r\) 表示这个树的根，由于本题没有给根，所以需要自己找一下。
状态转移方程设计：
-
如果当前节点不放置士兵，那么它的子节点必须全部放置士兵，因为要满足士兵可以看到所有的边。
则：\(f[x][0] += f[to][1]\)
\(to\) 是 \(x\) 的子节点。
-
如果当前节点放置士兵，它的子节点选不选已经不重要了，则取最小值即可。
则：\(f[x][1] += \min(f[to][0], f[to][1])\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1600;
struct node{
int to, next;
} a[N << 1];
int pre[N], k, dp[N][2], fa[N];
int n, c, idx, x;
vector<int> G[N];
void dfs(int x, int fath) {
dp[x][0] = 0, dp[x][1] = 1; // 边界条件
for (int i = 0; i < G[x].size(); i++) {
int to = G[x][i];
if (to != fath) { // 不能返回去
dfs(to, x);
dp[x][0] += dp[to][1];
dp[x][1] += min(dp[to][0], dp[to][1]);
}
}
}
int main() {
memset(fa, -1, sizeof(fa)); // 初始化
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &idx, &c);
for (int j = 1; j <= c; j++) {
scanf("%d", &x);
G[idx].push_back(x);
fa[x] = idx; // 记录每个节点的父亲，便于找根
}
}
int root;
for (int i = 0; i < n; i++) if (fa[i] == -1) root = i; // 找根
dfs(root, -1);
printf("%d", min(dp[root][0], dp[root][1]));
return 0;
}