题意:一城堡的所有的道路形成一个n个节点的树,如果在一个节点上放上一个士兵,那么和这个节点相连的边
就会被看守住,问把所有边看守住最少需要放多少士兵。
dproot[ i ]表示以i为根的子树,在i上放置一个士兵,看守住整个子树需要多少士兵。
all[ i ]表示看守住整个以i为根的子树需要多少士兵。
状态转移方程:
叶子节点:dproot[k] =1; all[k] = 0;
非叶子节点: dproot[i] = 1 + ∑all[j](j是i的儿子);
all[i] = min( dproot[i], ∑dproot[j](j是i的儿子)
),决策是否在i点放士兵
由于是两个数组纠缠在一起的转移方程,所以对于all[i]的最优性理解有点别扭。
以下是推出来的一点东西,复习的时候或许有用:
在all[i]的转移时,若
dproot[i] > ∑dproot[j],即
1 + ∑all[j] >
∑dproot[j],即∑all[j] >=
∑dproot[j],
又根据定义
∑all[j] <= ∑dproot[j],所以∑all[j]
== ∑dproot[j],
所以可以选择这样一种方案让以i为根的子树需要最少士兵守护
: 即让i的所有儿子j1,j2...
都放士兵(此时根 i 就不用放士兵了),且子树j1,j2...所放的士兵分别为dproot[j1],
dproot[j2]...
若dproot[i]
<= ∑dproot[j],同理可得
1 + ∑all[j] <=
∑dproot[j],此时可选这样的方案,
对根 i 的所有儿子jk都选守住以jk为根的子树的最优的方案(jk处不一定放了士兵),再在根 i 处
放一个士兵,所以此时 all[i] =
dproot[i]
= 1 + ∑all[j]。
于是就证明了状态转移方程的最有性。
#include <iostream> #include <cstdio> using namespace std; struct TREE_NODE { int first, next; //first为该结点第一个儿子的下标,next为该结点的兄弟的下标,没有为-1 int rtWith, all; //rtWith在根处放了士兵的最优方案, all守住子树的最优方案 } tree[1505]; int root; //整棵树的根结点 void DFS(int rt) { if (tree[rt].first == -1) { tree[rt].rtWith = 1; tree[rt].all = 0; return; } int sumRtWith = 0, sumAll = 0; int now = tree[rt].first; while (now != -1) { DFS(now); sumAll += tree[now].all; sumRtWith += tree[now].rtWith; now = tree[now].next; } tree[rt].rtWith = sumAll + 1; tree[rt].all = min(tree[rt].rtWith, sumRtWith); } void input_subtree(int &rt) { //输入以rt为根的子树 int i, sn, child, tmp; scanf ("%d: (%d)", &rt, &sn); if (sn) scanf("%d", &tmp); else { tree[rt].first = -1; return; } tree[rt].first = tmp; for (i = 2; i <= sn; i++) { scanf ("%d", &child); tree[tmp].next = child; tmp = child; } tree[tmp].next = -1; } int main() { int n, i, subtree; while (scanf ("%d", &n) != EOF) { input_subtree(root); for (i = 2; i <= n; i++) input_subtree(subtree); DFS(root); printf("%d\n", tree[root].all); } return 0; }