洛谷 P2279 [HNOI2003]消防局的设立 题解【树形DP】【解题报告】

点击量：192

    这个题真的有点毒瘤，发现现在的树形DP都好厉害啊……

目录

题目描述

2020年，人类在火星上建立了一个庞大的基地群，总共有\(n\)个基地。起初为了节约材料，人类只修建了\(n-1\)条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地\(A\)到基地\(B\)至少要经过\(d\)条道路的话，我们称基地\(A\)到基地\(B\)的距离为\(d\)。

 

由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过\(2\)的基地的火灾。

 

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。

 

输入输出格式

输入格式：

输入文件名为input.txt。

 

输入文件的第一行为\(n(n\le 1000)\)，表示火星上基地的数目。接下来的\(n-1\)行每行有一个正整数，其中文件第\(i\)行的正整数为\(a_i\)，表示从编号为\(i\)的基地到编号为\(a_i\)的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有\(a_i<i\)。

 

输出格式：

输出文件名为output.txt。

 

输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

 

输入输出样例

输入样例#1：

6
1
2
3
4
5

输出样例#1：

2

题解：

    这个题有树形DP和贪心两种解法。比较麻烦也比较经典的是树形DP，这里先简单提一下贪心：

因为一个点必须被保护，所以我们尽可能让保护特定点的消防局尽可能浅，这样可以尽可能多地覆盖分支。同时因为深度较深的点要求更严格，所以我们用类似拓扑排序的方式把它们排序；实际上在时间复杂度要求不高的情况下可以对每个点按深度进行排序，类似BFS，如果当前节点没有被覆盖，就去找它父亲的父亲，覆盖掉即可。时间复杂度为\(O(n\sim n\log n)\)。

    树形DP是比较麻烦的，但是比较有价值，磕了好久才弄出来的。

    每个点\(u\)距离覆盖它的点\(v\)距离一定不超过\(2\)，则\(|uv|\le 2\)。我们统一一个方向，就认为每个点可以被它下面的两个点照顾、或者去照顾上面两个点。但是这个“上面”不是绝对的，因为可能是自己的兄弟，此时深度是一样的，我们直接这样进行DP。

    设\(f_{(i,x)}\)表示\(i\)号节点处于\(\overrightarrow{x-2}\)的状态。\(\overrightarrow{x-2}\)表示这个节点向上覆盖的情况，当这个向量方向向下，说明被下面距离\(|\overrightarrow{x-2}|\)的节点覆盖，当这个向量方向向上，说明可以去覆盖上面距离\(|\overrightarrow{x-2}|\)的节点。

    这样就可以根据状态进行转移了。\(f_{(i,x)}\)表示当实际存在这个状态时的最小消防局数量；除非这个状态不合法，否则一定存在这样的状态，每个节点都有选或不选的分支。如果实在不合法，DP数组就置为inf，防止一些边界情况。

    为了保证上面所说的“实际存在这个状态”，而且合法，那么要保证不存在超过这个状态的点。也就是说，如果这个状态是被下面距离\(|\overrightarrow{x-2}|\)的节点覆盖，那么这个状态就不能有\(|\overrightarrow{x-3}|\)的节点参加贡献。这样一来，对于节点\(i\)满足这个条件的就是\(f_{(v,sta’)},(i,v)\in E,sta’>sta\)。因为实际的\(sta\)所在的范围是\([0,4]\)，这一部分就是关于更新DP数组的。

    然后是决策这个点加不加一个消防局。对一个点\(i\)来说，当且仅当它是消防局时才会出现\(f_{(i,4)}\)的状态，这个状态是可以从它儿子的任何状态（包括\(0\)，而且\(0\)存在的意义就是这个）转移而来的。

    最终的答案一定要保证根节点被覆盖了，答案就是\(\max_{2\le i\le 4}f_{(1,i)}\)。因为贪心没有水平我没写出来，所以没有贪心的代码w。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[2000];
int head[1010],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int f[1010][5];//fij是能朝出送j-2个,j=0表示欠2个
int Min(int x,int n)
{
    int minn=1e9;
    for(int i=n;i<5;++i)
        minn=min(minn,f[x][i]);
    return minn;
}
//要存离叶子的最长距离
int flag[1010];
void dfs(int x,int from)
{
    int g=0;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            dfs(e[i].n,x);
            flag[x]=max(flag[x],flag[e[i].n]+1);
            for(int j=0;j<4;++j)
                f[x][j]+=Min(e[i].n,j+1);
            g+=Min(e[i].n,0);
        }
    if(flag[x]<2)
        f[x][2]=1e9;
    if(flag[x]==0)
    {
        f[x][3]=1e9;
        f[x][0]=1e9;
    }
    //f[x][0]可以不更新
    //f[x][1]只欠一个自己 补不了 也不更新
    //f[x][2]恰好不欠 也是从下面更新过来的
    //f[x][3]能延伸一个 要补 可以从下面挑一个f[x][4]-Min(1)最小的
    int ans=1e9;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
            ans=min(ans,f[e[i].n][4]-Min(e[i].n,1));
    f[x][3]=f[x][0]+ans;//1满足的可以被3覆盖
    //f[x][4]是建立一个新的消防局
    f[x][4]=1+g;
    return;//f[x][0]充当了临时变量？
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,u;
    scanf("%d",&n);
    for(int i=2;i<=n;++i)
    {
        scanf("%d",&u);
        add(u,i);
    }
    dfs(1,1);
    printf("%d\n",min(min(f[1][2],f[1][3]),f[1][4]));
    return 0;
}