1077 皇宫看守（树形dp）

╰半夏微凉° 2022-09-14 02:31 98阅读 0赞

**1. 问题描述：**

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

**输入格式**

输入中数据描述一棵树，描述如下：第一行 n，表示树中结点的数目。第二行至第 n+1 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 i，在该宫殿安置侍卫所需的经费 k，该结点的子结点数 m，接下来 m 个数，分别是这个结点的 m 个子结点的标号 r1，r2，…，rm。对于一个 n 个结点的树，结点标号在 1 到 n 之间，且标号不重复。

**输出格式**

输出一个整数，表示最少的经费。

**数据范围**

1 ≤ n ≤ 1500

**输入样例：**

6  
1 30 3 2 3 4  
2 16 2 5 6  
3 5 0  
4 4 0  
5 11 0  
6 5 0

**输出样例：**

样例解释：  
在2、3、4结点安排护卫，可以观察到全部宫殿，所需经费最少，为 16 + 5 + 4 = 25。  
来源：[https://www.acwing.com/problem/content/description/1079/][https_www.acwing.com_problem_content_description_1079]

**2. 思路分析：**

分析题目可以知道这道题目实际上求解的是能够覆盖所有的点的最小花费，注意与[323题战略游戏][323]的区别，323题需要求解覆盖所有的边的最小花费，也即一条边中至少需要一个点来覆盖，只需要两个状态即可解决，dp\[u\]\[0\]表示不选当前根节点u的最小花费，dp\[u\]\[1\]表示选当前根节点u的最小花费，分两种情况讨论即可；而这道题目对于当前的根节点u其实是受到三种情况的影响，分别是子节点，父节点和自己（每一种情况对应不同的守卫情况），所以第二维使用两个状态已经不能够表示当前的所有状态，这里需要三个状态来表示所有可能的状态，对应的状态表示的含义如下：

*  dp\[u\]\[0\]表示u这个节点没有放置守卫并且被父节点看到的所有方案的最小花费
 *  dp\[u\]\[1\]表示u这个节点没有放置守卫并且被子节点看到的所有方案的最小花费
 *  dp\[u\]\[2\]表示u这个节点放置了守卫的所有方案的最小花费

当前的u作为根节点；对于dp\[u\]\[0\]是以当前的节点u作为根节点的最小花费，我们只需要考虑子节点的影响即可，因为在递归返回到上一层的时候（回溯）会更新到父节点放守卫的情况（当前节点的父节点一定会放置一个守卫从而返回到上一层的时候会使用这个状态进行更新），因为是父节点看到了当前的节点u，所以u的子节点可以放也可以不放守卫（不考虑子节点受到父节点影响的情况），对于这两种情况取一个min累加到当前的dp\[u\]\[0\]上即可；对于dp\[u\]\[2\]表示当前的节点u放置了守卫，我们也只需要考虑子节点的情况即可，子节点可以放也可以不放；对于dp\[u\]\[1\]比较麻烦我们需要枚举所有看到当前u的子节点k并且需要加上其余节点可放也可以不放的情况，我们可以在枚举u的子节点递归回溯的时候计算出所有子节点可放可不放的情况的总和s，使用s减去当前的可以看到当前节点u的最小花费就是除了当前节点k之外所有子节点的花费，枚举所有的子节点取一个min就是当前的dp\[u\]\[1\]，其实表示的是至少存在一个u的子节点能够看到u。

**3. 代码如下：**

from typing import List
    import sys
    # 设置递归的最大调用次数, 如果不设置会出现爆栈的问题, python3的最大递归调用次数在1000次左右
    sys.setrecursionlimit(1600)
    
    
    class Solution:
        def dfs(self, u: int, w: List[int], g: List[List[int]], dp: List[List[int]]):
            # 当前的根节点u表示放置了守卫所以一开始的权重为当前节点的权重
            dp[u][2] = w[u]
            s = 0
            # 先计算dp[u][0]和dp[u][2]这两个可以直接计算出结果
            for next in g[u]:
                self.dfs(next, w, g, dp)
                dp[u][0] += min(dp[next][1], dp[next][2])
                dp[u][2] += min(dp[next][0], dp[next][1], dp[next][2])
                # 计算s, 为后面计算dp[u][1]做准备
                s += min(dp[next][1], dp[next][2])
            dp[u][1] = 10 ** 9
            # 计算dp[u][1]
            for next in g[u]:
                # 枚举当前的子节点能够看到父节点的情况, 没有所有的子节点取一个min
                dp[u][1] = min(dp[u][1], min(dp[u][1], s - min(dp[next][1], dp[next][2]) + dp[next][2]))
    
        def process(self):
            n = int(input())
            # sta表示标记不是根节点的
            sta = [0] * (n + 1)
            # g的每一个元素都是一个列表可以用来存储当前节点的所有子节点编号
            g = [list() for i in range(n + 1)]
            w = [0] * (n + 1)
            for i in range(n):
                t = list(map(int, input().split()))
                a, c = t[0], t[1]
                w[a] = c
                if t[2]:
                    # 由输入可以知道这是一个有向图, 所以存储一个一条边即可
                    for j in range(3, len(t)):
                        b = t[j]
                        g[a].append(b)
                        # 标记不是叶节点的节点
                        sta[b] = 1
            # 第二维存在三个状态
            dp = [[0] * 3 for i in range(n + 1)]
            root = 1
            # 找到根节点
            while sta[root]: root += 1
            self.dfs(root, w, g, dp)
            # 以当前的root作为根节点能够被子节点看到和自身看到的较小值就是答案, 根节点是不能够被父节点看到的
            return min(dp[root][1], dp[root][2])
    
    
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_description_1079]: https://www.acwing.com/problem/content/description/1079/
[323]: https://blog.csdn.net/qq_39445165/article/details/120562867