[题解] Luogu – 2016 战略游戏

题目描述

Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。

他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵.

输入格式

第一行 $N$ ，表示树中结点的数目。

第二行至第 $N+1$ 行，每行描述每个结点信息，依次为：该结点标号 $i$ ，$k$ (后面有 $k$ 条边与结点 $I$ 相连)。

接下来 $k$ 个数，分别是每条边的另一个结点标号 $r_1$，$r_2$，…，$r_k$。

对于一个 $n$ ( $0 < n \leq 1500 $ )个结点的树，结点标号在 $0$ 到 $n-1$ 之间，在输入数据中每条边只出现一次。

输出格式

输出文件仅包含一个数，为所求的最少的士兵数目。

样例输入

4
0 1 1
1 2 2 3
2 0
3 0

样例输出

1

解题思路

考虑树形 $DP$，本题和没有上司的舞会非常相似

令数组 $f[i][0/1]$ 表示节点 $i$ 上放置士兵或不放置士兵时完全覆盖节点 $i$ 的子树的最小士兵数目

那么
$$f[i][0] \leftarrow f[v][1]$$

$$
f[i][1] \leftarrow (f[v][0], f[v][1])_{min}
$$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 1500 + 10;
const int MAXM = 3000 + 10;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

int Head[MAXN], to[MAXM], Next[MAXM], tot = 1;
int f[MAXN][2];

inline void dfs(int x, int fa){
    f[x][1] = 1;

    for(register int i=Head[x]; i; i=Next[i]){
        int v = to[i];

        if(v != fa){
            dfs(v, x);

            f[x][0] += f[v][1];
            f[x][1] += min(f[v][0], f[v][1]);
        }
    }   
}

inline void add(int a, int b){
    to[tot] = b;
    Next[tot] = Head[a];
    Head[a] = tot++;
}

int n;

int main(){
    n = read();

    for(register int i=1; i<=n; i++){
        int id = read();
        int k = read();

        for(register int j=0; j<k; j++){
            int v = read();

            add(id, v);
            add(v, id);
        }
    }

    dfs(0, -1);

    printf("%d", min(f[0][0], f[0][1]));
    return 0;
}