IOI2005 [动态规划树形DP] 河流

89 阅读 0 评论 59 点赞

我是靠谱客的博主兴奋康乃馨，最近开发中收集的这篇文章主要介绍IOI2005 [动态规划树形DP] 河流，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背景

安徽省芜湖市集训队练习题
IOI 2005 Rivers(riv)
Description:Amber
Data:Official
Program:JackDavid127

描述

几乎整个Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——Bytetown。
在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。
注：所有的河流都不会分叉，形成一棵树，根结点是Bytetown。
国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米1分钱。
编一个程序：
1．从文件读入村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。
2．计算最小的运费并输出。

格式

输入格式

第一行包括两个数n（2<=n<=100），k（1<=k<=50,且k<=n）。n为村庄数，k为要建的伐木场的数目。除了Bytetown 外，每个村子依次被命名为 1，2，3……n，Bytetown被命名为0。
接下来n行，每行3个整数：
wi——每年 i 村子产的木料的块数。（0<=wi<=10000）
vi——离 i 村子下游最近的村子。（即 i 村子的父结点）（0<=vi<=n）
di——vi 到 i 的距离(千米)。（1<=di<=10000）
保证每年所有的木料流到bytetown 的运费不超过2000,000,000分
50％的数据中n不超过20。

输出格式

输出最小花费，精确到分。

样例

样例输入
4 2
1 0 1
1 1 10
10 2 5
1 2 3
样例输出
4

提示

树形动态规划
经典问题

来源

安徽省芜湖市集训队练习题
IOI 2005 Rivers(riv)
Description:Amber
Data:Official
Program:JackDavid127

我想如果就算提示不说这好似树形dp，也很好判断这是（废话= =），好吧这题以我的能力的确是做不出来，然后在网上又跟随了一个错误的领导者…对着错的程序看了半天…最后还是在错误的基础上改对了。改到心累。（左右儿子表示码错，改了好久QAQ）

题目大意可以这样理解：每个节点有一个带有权值的点，这个点可以就地消掉，也可以通过带有权值的边送到它的父亲节点，要求所有点都消掉的最小代价。

首先需要了解的知识点就是多叉树转二叉数，也就是左儿子右兄弟。然后就可以从后往前dp。至于实现从后往前的方法，可以递归实现，也可以实现预处理一下，搜一遍将转换后的二叉树，让每个节点的儿子和兄弟在新序列的后面。两种方法皆可。

至于状态转移方程，用 f[i][j][k] 表示目前考虑第 i 个点， j 表示 i 所有的祖先中离 i 最近并且建了伐木场的节点， i 的儿子以及 i 的兄弟一共建了 k 个伐木场。那么对于 i 这个点就有两种选择：1、不在这个节点建造伐木场。2、在这个节点建。
转移如下：
（在）f[i][j][k]=min(f[i][j][k],f[leftson][i][l]+f[rightson][j][k-l-1])
（不在）f[i][j][k]=min(f[i][j][k],f[leftson][j][l]+f[rightson][j][k-l]+val[i]*(dis i..j))

这里解释一下：

在这个节点建伐木场时， i 的儿子们就可以直接送到 i 节点，因此左儿子为 f[leftson][i][l] ；但 i 的兄弟们无法到达 i ，所以它们依然需要送到 j （离 i 最近并且建了伐木场的节点），因此右儿子为 f[rightson][j][k-l-1] 。另外，由于 i 建造用去一个伐木场，所以方程中的第三维需减一。

不在这里建时，左右儿子都需送到 j ，但还要加上 i 点权 * i..j 的距离。这个很好理解，但是此处不需要处理 i..j 节点中的节点的点权，因为此处只考虑 i 点， i..j 的节点以后可以推出。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
    int left,right,num,dis;
}gg[105];
int dui[105],deep[105],child[105],f[105][105][51],tot,fa[105];
const int INF=0x7f7f7f7f;
void dfs(int k,int dep)//生成从后往前推的序列
{
    dui[++tot]=k;
    deep[k]=dep+gg[k].dis;
    int i=gg[k].left;
    while(i)
    {
        dfs(i,deep[k]);
        i=gg[i].right;
    }
}
int main()
{
    int n,K;
    cin>>n>>K;
    memset(fa,-1,sizeof fa);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(!child[b])
            gg[b].left=i;
        else
            gg[child[b]].right=i;
        child[b]=i;
        gg[i].num=a;
        gg[i].dis=c;
        fa[i]=b;
    }//多叉转二叉 
    dfs(0,0);
    memset(f,INF,sizeof f);//需要赋初值
    memset(f[0],0,sizeof f[0]);//
    for(int i=n+1;i>=2;i--)
    {
        int now=dui[i];
        int le=gg[now].left;
        int ri=gg[now].right;
        for(int j=fa[now];j!=-1;j=fa[j])//枚举父亲节点 
            for(int k=0;k<=K;k++)
            {
                for(int l=0;l<=k;l++)//不选 i
                    if(f[le][j][l]!=INF&&f[ri][j][k-l]!=INF)
                    {
                        int add=gg[now].num*(deep[now]-deep[j]);
                        int op=f[le][j][l]+f[ri][j][k-l]+add;
                        f[now][j][k]=min(f[now][j][k],op);
                    }
                for(int l=0;l<k;l++)//选 i
                    if(f[le][now][l]!=INF&&f[ri][j][k-l-1]!=INF)
                    {
                        int op=f[le][now][l]+f[ri][j][k-l-1];
                        f[now][j][k]=min(op,f[now][j][k]);
                    }
            }
    }
    printf("%d",f[gg[0].left][0][K]);
}