[IOI2005]Riv 河流

题目描述

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

输入

输入格式 Input Format
   　　第一行包括两个数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。

输出

输出最小花费，精确到分

样例输入

样例输出

一道dp好题，希望借此稍微对dp算法的构思进行下探究

第一步：化简问题

化简问题既是对包装好的复杂题面的化简，也是对题目性质的初步探究。这一步非常关键，我在第一次做的时候这里就出现了问题……

当时化简成了“先统计经过每条路的数量，再把每条路的贡献加到一起”，这个化简得错误就在于没有注意到我们可以把木材集中与他的生产点上考虑

这样去考虑就无形的把本来是一个点上的问题拆成了许多条边上的问题。。。

这也体现了当一个思路不通时，要及时的改变思路，不要硬钻牛角尖

正确的化简姿势：每个节点有一个权值，然后在树上选择

能全面的表达当前形势。能够不产生歧义，且对状态的转移产生影响的所有变量都有涵盖
没有后效性。dp状态拆分出来的子问题应该能够在自己内部单独解决，而不需要考虑问题之间的影响

针对这道题，一个很自然的思路是设 f(i,k)，表示以i为节点的子树中，建了k个伐木场，里面每个节点的木材产生贡献的总和的最小值

但我们发现一个问题，这个状态并不唯一，我们发现这个值受离子树最近的伐木场影响

所以拓充状态为 f(i,j,k) j表示j为i及其祖先中离i最近的伐木场，k个伐木场中不算这个

这样发现状态的不足对其进行补充是需要加强的一点，有的时候也需要推翻重新设计状态

第三步：转移

这一步就因题而异了，要强调一点的就是要灵活运用数据结构，不要被类似题限制住了

首先对i的儿子们来说相当于是一个一个子树的接，因此考虑使用背包dp的形式处理

f(i,j,k)=min{f(i,j,k-x)+f(v,j,x)};

最后再 f(i,j,k)+=s[i]*(dep[i]-dep[j]) s[i]是这个点的权值

然后当他的祖先们再用的侯，如果i==j的话就不对了，所以所有的f(i,j,k)都要被更新一发f(i,i,k-1)（在计算的时候没有考虑自己这个位置上的消耗，所以-1）

来看看代码吧~：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,K,size,vi,di,etop;
 5 int sum[501],nxt[1001],to[1001],w[1001],h[501],sta[1001],dep[1001];
 6 long long f[111][111][51];
 7 void add(int x,int y,int dis){
 8     etop++;nxt[etop]=h[x];h[x]=etop;to[etop]=y;w[etop]=dis;
 9 }
10 void dfs(int i){
11     sta[++size]=i;
12     for(int t=h[i];t;t=nxt[t]){
13         int v=to[t];
14         dep[v]=dep[i]+w[t];
15         dfs(v);
16         for(int j=1;j<=size;j++)
17             for(int k=K;k>=0;k--){
18                 f[i][sta[j]][k]+=f[v][sta[j]][0];
19                 for(int x=0;x<=k;x++)
20                     f[i][sta[j]][k]=min(f[i][sta[j]][k],f[i][sta[j]][k-x]+f[v][sta[j]][x]);
21             }
22     }
23     for(int j=1;j<=size;j++)
24         for(int k=0;k<=K;k++){
25             if(k>=1)
26                 f[i][sta[j]][k]=min(f[i][sta[j]][k]+sum[i]*(dep[i]-dep[sta[j]]),f[i][i][k-1]);
27             else
28                 f[i][sta[j]][k]+=sum[i]*(dep[i]-dep[sta[j]]);
29         }
30     size--;
31 }
32 int main(){
33     scanf("%d%d",&n,&K);
34     for(int i=1;i<=n;i++){
35         scanf("%d%d%d",&sum[i],&vi,&di);
36         add(vi,i,di);
37     }
38     dfs(0);
39     printf("%d
",f[0][0][K]);
40     return 0;
41 }

View Code

这里在转移时利用了栈

双倍经验还有：https://www.luogu.org/problemnew/show/CF1082F