战略游戏（LGOJ P2016） —— 树形DP基础

古城微笑少年丶 2022-03-08 07:49 300阅读 0赞

**目录**

题目

题目描述

输入

输出

样例输入

样例输出

提示

解析

参考代码

--------------------

# 前言 #

为什么库存里还有一个这个呢？？

算了既然忘记发了那就发了吧。。。

# 题目 #

## 题目描述 ##

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

他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

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

## 输入 ##

输入数据表示一棵树，描述如下：

第1行: 1个整数N(0＜N≤1500)，表示树中结点的数目。

第2行..第N+1行: 每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点i相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。

对于一个N个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次

## 输出 ##

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

## 样例输入 ##

样例1

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

样例2

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

## 样例输出 ##

样例1

样例2

## 提示 ##

样例一示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70][]

样例二示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1][]

# 解析 #

其实这道题乍一看好像跟[手机网络\[USACO 08 JAN\]][USACO 08 JAN]差不多，于是我在看完题以后也就真的把源代码改了下输入后就交了。。。。

可能大家都已经知道了结果会是什么—— ***Wrong Answer*** .（***此处应有《凉凉》***）

于是乎，我又重新看了下题目描述，最后终于发现了一个很重要的东西 ——

> 他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的***路***。 注意，某个士兵在一个结点上时，与该结点相连的**所有*边***将都可以被瞭望到。

这就是与那道题的不同点了：手机网络实际上求得是节点，也就是说一个节点建了信号塔，那么与它相邻的***节点***就可以“一衣带水”不用再建了，但是这道题就不一样了，如果说这个点放上了士兵，那么受益的其实是与它相邻的***边***。

如果大家还是没有懂的话，可以看这个图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2][]

如果按手机网络的话，最优的方案就是在1号节点，2号节点和4号节点分别放上信号塔，最后是有三个。

而如果是按照本题来看的话，那么最优的方案其实是2号节点，3号节点和4号节点放上士兵。虽然来说也是有三个，但是这两个的3却代表着不一样的意思。

而这个差异到一些数据更大的时候就会更加明显，甚至答案也会不一样哦。

讨论完差距，现在来设dp吧。

我们可以令![dp\_\{i, j\}][dp_i_ j]表示为以i为根的子树中，i是否放士兵的分别最小士兵数量。

通俗点来说，就是j一共有2种——![\{\\color\{Red\} dp\_\{i, 0\}\}][color_Red_ dp_i_ 0]表示i放上士兵的状态，而![\{\\color\{Red\} dp\_\{i, 1\}\}][color_Red_ dp_i_ 1]则表示不放。

这样来看的话，其实状态是比较好推出来的——

![dp\_\{i, 0\} += min\\left \\\{ dp\_\{son, 0\}, dp\_\{son, 1\} \\right \\\}][dp_i_ 0_ _ min_left _ dp_son_ 0_ dp_son_ 1_ _right]，因为i放上了士兵，那么他的儿子放不放也就无所谓了。

![dp\_\{i, 1\} = min\\left \\\{ dp\_\{son, 1\} \\right \\\}][dp_i_ 1_ _ min_left _ dp_son_ 1_ _right]i不放士兵的话，那么就必须靠它的儿子来将他们之间的那条边瞭望到了。

## 参考代码 ##

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    using namespace std;
    #define min(a, b) a < b ? a : b
    #define max(a, b) a > b ? a : b
     
    void read (int &x){
        int f = 1; x = 0;
        char c = getchar ();
        while (c < '0' || c > '9'){
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
     
    void print (int x){
        if (x < 0){
            putchar ('-');
            x = ~(x) + 1;
        }
        if (x / 10) print (x / 10);
        putchar (x % 10 + 48);
    }
     
    #define N 1500
    #define INF 0x3f3f3f3f
     
    int n, dp[N + 5][3], root, indeg[N + 5];
    vector <int> G[N + 5];
     
    void dfs (int u, int f){
        dp[u][0] = 1;
        for (int i = 0; i < G[u].size (); i++){
            int v = G[u][i];
            if (v == f) continue;
            dfs (v, u);
            dp[u][0] += min (dp[v][1], dp[v][0]);
            dp[u][1] += dp[v][0];
        }
    }
     
    int main (){
        read (n);
        for (int i = 1; i <= n; i++){
            int u, k; read (u); read (k);
            while (k--){
                int v; read (v);
                G[u].push_back (v);
                indeg[v] ++;
            }
        }
        for (int i = 0; i < n; i++)
            if (!indeg[i]){
                root = i;
                break;
            }
        dfs (root, -1);
        print (min (dp[root][0], dp[root][1]));
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220308/032e818d537840db98bb17b1c52212f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220308/015c04c7de934edd86572bc2b3538ed2.png
[USACO 08 JAN]: https://www.luogu.org/problemnew/show/P2899
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220308/54362475351441f397ea6310e85c5a79.png
[dp_i_ j]: https://private.codecogs.com/gif.latex?dp_%7Bi%2C%20j%7D
[color_Red_ dp_i_ 0]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BRed%7D%20dp_%7Bi%2C%200%7D%7D
[color_Red_ dp_i_ 1]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BRed%7D%20dp_%7Bi%2C%201%7D%7D
[dp_i_ 0_ _ min_left _ dp_son_ 0_ dp_son_ 1_ _right]: https://private.codecogs.com/gif.latex?dp_%7Bi%2C%200%7D%20&plus;%3D%20min%5Cleft%20%5C%7B%20dp_%7Bson%2C%200%7D%2C%20dp_%7Bson%2C%201%7D%20%5Cright%20%5C%7D
[dp_i_ 1_ _ min_left _ dp_son_ 1_ _right]: https://private.codecogs.com/gif.latex?dp_%7Bi%2C%201%7D%20%3D%20min%5Cleft%20%5C%7B%20dp_%7Bson%2C%201%7D%20%5Cright%20%5C%7D