树形DP | 1：—— 例题：小游戏

男娘i 2023-07-17 04:46 22阅读 0赞

## 小游戏 ##

某人很喜欢玩计算机游戏，特别是战略游戏，但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗？

你的任务是给出士兵的最少数目。

输入包含多组数据。每组数据表示一棵树，在每组数据中：

第一行是结点的数目。

接下来的几行，每行按如下格式描述一个结点：

结点标识符 : ( 道路的数目 ) 结点标识符1  结点标识符2  ......  结点标识符道路的数目

或者

结点标识符 : (0)

对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。

对于每组数据，各给出一个整数表示士兵的最少数目.

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入</th> 
   <th>期待的输出</th> 
   <th>时间限制</th> 
   <th>内存限制</th> 
   <th>额外进程</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td>&nbsp; 
    <ol> 
     <li>4↵</li> 
     <li>0:(1)&nbsp;1↵</li> 
     <li>1:(2)&nbsp;2&nbsp;3↵</li> 
     <li>2:(0)↵</li> 
     <li>3:(0)↵</li> 
     <li>5↵</li> 
     <li>3:(3)&nbsp;1&nbsp;4&nbsp;2↵</li> 
     <li>1:(1)&nbsp;0↵</li> 
     <li>2:(0)↵</li> 
     <li>0:(0)↵</li> 
     <li>4:(0)↵</li> 
    </ol></td> 
   <td>&nbsp; 
    <ol> 
     <li>1↵</li> 
     <li>2↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

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

本题给出了一颗树，需要在若干节点上部兵，使得他们能看到所有的边。

## 1、对输入的处理 ——  图的存储 ##

本题的树，也就是一个无向连通无环图。考虑用 邻接链表 来储存。（会采用vector容器简化链表的操作）

题目表明：每一条边只会输入一次。也就是说，对于边ab在输入时，如果在点a后输入了b，那么在点b后就不会再输入a了。而此题的图是一个无向图，为了方便我们的一般化对图的遍历，应该在处理输入且构建图时，要将两点之间的边补全：即对于边ab，我们可以通过b访问到a，也可以通过a访问过b。

## 2、动态寻求最优部署 —— 深搜 ##

为确保每一条边都需要能被看到，那么每条边的两个端点中必须至少有一端有士兵。每一个点有两种选择：放士兵、不放士兵。且根据树的结构特点：根节点 root 下有若干子节点，每一个字节点和其后裔又可以看作一棵子树。那么我们可以采用深搜：搜索root根节点，然后依次对 root 的每一棵子树继续搜索。（第一次root可以随便选择）

**使用一个二维数组 dp\[0..n-1, 0..1\] 来记录最少人数 ：**

*  dp\[root\]\[0\]：当 root 节点不放士兵时，以 root 为根的树需要的最少人数
 *  dp\[root\]\[1\]：当 root 节点放士兵时，以 root 为根的树需要的最少人数

**本题应该是自底向上的解法：**

先将子树(设其节点为next)的dp\[next\]\[0\]、dp\[next\]\[1\]计算出来，在此基础上才能计算子树上一层的树(设其节点为root)的dp\[root\]\[0\]、dp\[root\]\[1\]。最终的答案应该是dp\[root\]\[0\]、dp\[root\]\[1\]中的较小值。

**构建状态方程：**

那么如何从子树的结果迁移到整体的树呢？分两种：

*  如果 root 节点不放兵：其每一个子节点next必须放兵，必须选择 dp\[next\]\[1\]
 *  如果 root 节点放兵：其每一个子节点next可以放兵也可以不放兵，应该选择 dp\[next\]\[0\] 与 dp\[next\]\[1\] 中的较小值，再加上root本身的一个

故状态转移方程如下：

![dp\[root\]\[0\] = \\sum dp\[next\]\[1\]][dp_root_0_ _ _sum dp_next_1]

![\\bg\_white dp\[root\]\[1\] =1 + \\sum min(dp\[next\]\[0\], dp\[next\]\[1\])][bg_white dp_root_1_ _1 _ _sum min_dp_next_0_ dp_next_1]

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

完整AC代码：

//
    // Created by LittleCat on 2020/3/10.
    //
    
    #include <cstdio>
    #include <cstring>
    #include <bits/stdc++.h>
    
    using namespace std;
    #define MAX 1550
    
    vector<int> point[MAX]; //map[i]储存节点i的临接节点集
    bool vis[MAX];  //vis[i]表示节点i是否被访问过
    int dp[MAX][2];
    
    void DFS(int root) {
        vis[root] = true;   //标记已访问节点
        /* 依次遍历根节点的每一个子节点 */
        for (int i = 0; i < point[root].size(); i++) {
            int next = point[root][i];   //子节点
            if (vis[next])   //是已访问的前驱节点
                continue;  //避免往回搜索
            DFS(next);  //搜索子节点
            dp[root][0] += dp[next][1];
            dp[root][1] += min(dp[next][0], dp[next][1]);
        }
        dp[root][1]++;
    }
    
    int main() {
        int n;
        while (EOF != scanf("%d", &n)) {
            /* 初始化数组 */
            for (auto & i : point)
                i.clear();
            memset(vis, false, sizeof(vis));
            memset(dp, 0, sizeof(dp));
            /* 处理输入 */
            for (int i, k; n; n--) {
                scanf("%d:(%d)", &i, &k);  //前驱节点i,边数k
                for (int j; k; k--) {
                    scanf("%d", &j);  //后继节点j
                    point[i].push_back(j);
                    point[j].push_back(i);
                }
            }
            int root = 0;
            DFS(root);
            printf("%d\n", min(dp[root][0], dp[root][1]));
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

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

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

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

欢迎关注个人公众号“ 鸡翅编程 ”，这里是认真且乖巧的码农一枚。

\---- 做最乖巧的博客er，做最扎实的程序员 ----

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]

[dp_root_0_ _ _sum dp_next_1]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Broot%5D%5B0%5D%20%3D%20%5Csum%20dp%5Bnext%5D%5B1%5D
[bg_white dp_root_1_ _1 _ _sum min_dp_next_0_ dp_next_1]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Broot%5D%5B1%5D%20%3D1%20&plus;%20%5Csum%20min%28dp%5Bnext%5D%5B0%5D%2C%20dp%5Bnext%5D%5B1%5D%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/c4f47b5e89504832aa30f9c940ddf392.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/f6525d2c8ca54d90b9c6008e27859891.png