题目描述
几乎整个Byteland王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown
在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在 运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。
注意：所有的河流都不会分叉，也就是说，每一个村子，顺流而下都只有一条路——到bytetown。
国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一块木料每千米1分钱。
编一个程序：
1．从文件读入村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。
2．计算最小的运费并输出。
输入
第1行：包括两个数 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
说明
下图是样例输入的说明。圈内数字为村庄编号，下方数字为存储木料块数，边权为河的长度。伐木场应建在村庄2和3。
应该比较好看出来这是一道树形dp，而dp方程式有点难想，刚开始时自己想只有两维，分别是当前村庄i，和所需建的伐木场个数k。然后怎么想也想不出来，于是就搜了一下题解。
下面是搜出来的题解代码（有改动）
#include<iostream>
#include<cmath>
#include<climits>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef unsigned long long uLL;
const unsigned long long inf=2000000005;
const int MAXN=100;
using namespace std;
struct node{int rc,lc,w,d;}tree[MAXN+5];
int cnt,n,K,a,dist[MAXN+5],H[MAXN+5],fa[MAXN+5];
uLL F[MAXN+5][MAXN+5][55];
bool vis[MAXN+5];
void dfs(int s,int deep){
H[++cnt]=s; vis[s]=1; dist[s]=deep;
for(int i=tree[s].lc;i;i=tree[i].rc)
if(!vis[i]) dfs(i,deep+tree[i].d);
}
inline void Read(int &Ret){
char ch; bool flag=0;
for(;ch=getchar(),ch<'0'||ch>'9';)if(ch=='-') flag=1;
for(Ret=ch-'0';ch=getchar(),'0'<=ch&&ch<='9';Ret=Ret*10+ch-'0');
flag&&(Ret=-Ret);
}
int main()
{
Read(n); Read(K);
memset(fa,-1,sizeof(fa));
for(int i=1;i<=n;i++)
{
Read(tree[i].w); Read(a); Read(tree[i].d);
tree[i].rc=tree[a].lc;
tree[a].lc=i; fa[i]=a;
}
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=H[i];
int lson=tree[now].lc,rson=tree[now].rc;
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[lson][j][l]!=inf&&F[rson][j][k-l]!=inf)
{
uLL add=(uLL)tree[now].w*(dist[now]-dist[j]);
F[now][j][k]=min(F[now][j][k],F[lson][j][l]+F[rson][j][k-l]+add);
}
for(int l=0;l<k;l++)//选 i
if(F[lson][now][l]!=inf&&F[rson][j][k-l-1]!=inf)
F[now][j][k]=min(F[now][j][k],F[lson][now][l]+F[rson][j][k-l-1]);
}
}
printf("%llu",F[tree[0].lc][0][K]);
}
第一眼看过去的时候就觉得很诡异，因为这位大神竟然没有用到递归，而是直接套了四层循环搞了出来。
dp的状态有三维：
用 f[i][j][k] 表示目前考虑第i个点,j表示i所有的祖先中离i最近并且建了伐木场的节点,i的儿子以及i的兄弟一共建了k个伐木场。
（在i建）f[i][j][k]=min(f[i][j][k],f[lson][i][l]+f[rson][j][k-l-1])
（不在i建）f[i][j][k]=min(f[i][j][k],f[lson][j][l]+f[rson][j][k-l]+val[i]*(dis[i][j]))
这是直接copy的那位大神的叙述。应该是比较清晰的。注意这是已经转成二叉数后的方程式。
解释一下：
当在i建时，离i最近的伐木场自然是i本身，而他的兄弟节点（也就是他的rson，转了二叉），最近的依然是j，因为i已建立伐木场，所以i的儿子还有l个伐木场可建，而兄弟就还有k-l-1个伐木场可建
而不在i建时，离i和它的兄弟们最近的伐木场自然仍然是j，其余同上。而这时需要加上木材运到j的花费了（上面的那种状态不用的原因是因为还未确定是否在除i以外的其他节点建造伐木场，i本身是没有花费的）
都说编程有三难：思路难，代码难，调试难。
将思路解决了，在来看看这个不用递归的神奇代码
在处理输入的时候就是把多叉转成二叉，并没有什么特殊的处理。
而需要注意的是dfs：
这个dfs首先会将每个节点距根节点的距离处理出来，存储在dist数组中
然后给每个节点赋予一个按照先序遍历的顺序的编号，在枚举节点的时候，就是按这个编号的从大到小来枚举的。
那么为什么可以按照先序遍历来处理呢？
画个图可以发现，每一个子树本身必定大于它的所有的儿子节点，或者更准确地说，对于每一个子树i，它的编号都刚好比它的某个儿子小1，也就意味着，除叶子节点以外，每个节点都能保证它所有儿子节点都处理完后再来处理它本身，那么恰好满足dp的状态转移所需要的顺序了。（表示深深的膜拜）
然后是有一句话
memset(F[0],0,sizeof(F[0]));
我之前一直都没想通，为何要把它清为0。
后来有点明白了。
注意，这里的F[0]并不是指的根节点，而是指叶子节点的下方节点，如果它们的值也是inf，那么你会发现，dp是跑不动的。
然后就没啥了，其余还有点细节问题
再次表示深深的膜拜
最后
以上就是呆萌仙人掌最近收集整理的关于树形dp（IOI 2005河流代码理解）的全部内容，更多相关树形dp（IOI内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[CODEVS1378]选课（树形dp）](/uploads/reation/bcimg10.png)
![bzoj 1812: [Ioi2005]riv （树形dp+多叉树转二叉树）](/uploads/reation/bcimg1.png)
发表评论 取消回复