猫史档案馆

状压dp回顾

之前发了一个状压dp。

状压DP是将一个状态转化成一个数，然后用位运算进行状态的处理。除了这一点，其实就跟普通的DP没有什么两样。

详情：https://shequ.codemao.cn/community/224373

切入正题：树形dp

 

我们以一个例题为例。

 

【例】皇宫看守
问题描述：
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

 

编程任务：
帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

 

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

第1行 n，表示树中结点的数目。

第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的喵数m，接下来m个数，分别是这个节点的m个喵的标号r1，r2，…，rm。

对于一个n（0 < n<=1500）个结点的树，结点标号在1到n之间，且标号不重复。

 

数据输出：
输出文件仅包含一个数，为所求的最少的经费。

样例输入：
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出：
25

 

分析

 

题目说的很清楚，用最少的经费覆盖所有的点。如果是一个图的话，它是个NP完全问题，但题目给出的是个树，避免了后效性的问题，所以可以用动态规划来解决。

 

给出如下定义：

F[i,0]表示i点不放，且以i为根节点的子树（包括i节点）全部被观察到；

F[i,1]表示i点不放，且以i为根节点的子树（可以不包括i节点）全部被观察到；

F[i,2]表示i点放，且以i为根节点的子树全部被观察到；

 

转移如下：

1、由F[i,0]定义可知，设j为i的喵节点，至少要有一个i的喵节点是放置守卫的，其余的喵节点可放可不放，但由于根节点i不放，所以其余的喵节点如果不放的话，必须保证能被观察到，即F[j][0]；所以我们需要枚举必须放置的喵节点，下面的转移方程描述的很清楚:

F[i,0] = min{Sigma(min(F[j][0],F[j,2]))+F[k,2]}，

其中k为枚举的必放的喵节点，j为除了k之外的喵节点

2、由F[i,1]定义可知，i可以被观察到也可以不被观察到,但喵节点必须都要被观察到，转移如下：

F[i,1] = Sigma(min(F[j,0],F[j,2]))

 j是i的喵节点

3、由F[i,2]定义可知，i点放置了守卫，所以对于每个喵节点都能被观察到，取F[j,0],F[j,1],F[j,2]最小值即可：

F[i,2] = min(F[j,0],F[j,1],F[j,2])

j是i的喵节点

 

4、对于叶节点i，

F[i,0] = F[i,2] = data[i],F[i,1] = 0;

 

 

//
//  皇宫看守.cpp
//  树形DP
//

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

using namespace std;

const int maxn = 1500+10;

int f[maxn][3],data[maxn],n,son[maxn][maxn],len[maxn],du[maxn],x,root;

void doit(int x)//当前正在考虑x节点
{
    if (len[x] == 0)//没有子节点，即叶节点
    {
        f[x][0] = f[x][2] = data[x];
        f[x][1] = 0;
        return;
    }
for (int i = 1;i <= len[x];i++)
        doit(son[x][i]);
//为了找到叶节点确定边界条件，先拼命深搜下去，
//直到触发上面的if语句找到叶子节点确定边界条件，
//然后在一起回溯到最开始那层，并进行下面的操作。

    f[x][0] = INT_MAX;                  //开始求f[x][0]的最优值。
    for (int i = 1;i <= len[x];i++)     //遍历子节点
    {                                   //第i个子节点作为安放卫兵的最优值。
        int 喵p = 0;                    //喵p用于计第i个子节点作为安放卫兵的i兄弟节点所需经费的最优值。
        for (int j = 1;j <= len[x];j++) //找出i的兄弟节点
            if (i!=j)
                喵p += min(f[son[x][j]][0],f[son[x][j]][2]);//由于父节点没有安放卫兵，
//所以子节点j必须被j的子树中的节点覆盖。
//这里求j节点的最优值，喵p加上这个兄弟节点最优值。
        f[x][0] = min(f[x][0],喵p+f[son[x][i]][2]);//原来的安放方法，以及使用新的子节点i安放卫兵的方法中取最优值，
//转移到f[x][0]的状态中。
    }
    f[x][1] = 0;                        //开始求f[x][1]的最优值。
    for (int i = 1;i <= len[x];i++)
       f[x][1] += min(f[son[x][i]][0],f[son[x][i]][2]);//节点x的子树必须覆盖，
//因此其子节点也必须覆盖，
//子节点的两个状态的更优解转移到x节点的状态中
    f[x][2] = data[x];                 //开始求f[x][2]的最优状态
    for (int i = 1;i <= len[x];i++)
        f[x][2] += min(f[son[x][i]][0],min(f[son[x][i]][1],f[son[x][i]][2]));//由于x节点已经覆盖，
//所以子节点也覆盖了，子节点3个状态取最优状态转移。
//之所以要这么写是因为min函数只能对两个值取较小的一个，3个就不行，
//所以要嵌套一下。
}

int main()
{
    scanf("%d",&n);
    memset(data,0,sizeof(data));             //存每个点放置守卫的代价
    memset(f,0,sizeof(f));                   //dp数组，F[i,j]含义如上述分析
    memset(du,0,sizeof(du));                 //存储每个点的入度，用于找出根节点
    memset(son,0,sizeof(son));               //存储每个点的喵节点
    memset(len,0,sizeof(len));               //存储每个点喵节点个数
    for (int i = 1;i <= n;i++)
    {
        scanf("%d",&x);
        scanf("%d%d",&data[x],&len[x]);
        for (int j = 1;j <= len[x];j++)
        {
            scanf("%d",&son[x][j]);// x节点的（其中一个）孩子是j结点
            du[son[x][j]]++;// j节点的入度由x节点提供
        }
    }
    for (int i = 1;i <= n;i++)
        if (du[i] == 0)  //如果其中一个结点没有入度，就是根节点
        {
            root =i;//找到根节点，root定位
            break;
        }
        doit(root);//从根节点开始
    printf("%d\n",min(f[root][0],f[root][2]));//由于根节点也要覆盖，
                                              //所以f[root][1]不行。从0和2的最优值中再选出一个最优值。
    }
    return 0；
}