【bzoj1812】[Ioi2005]riv

2015.06.03 16:48 Wed | 28次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

第一行 包括两个数 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村子下游最近的村子(或bytetown)(0<=vi<=n) di——vi到i的距离(km)。(1<=di<=10000) 保证每年所有的木料流到bytetown的运费不超过2000,000,000分 50%的数据中n不超过20。

Output

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

Sample Input

4 2
1 0 1
1 1 10
10 2 5
1 2 3

Sample Output

4

题解

自己的代码能力真的是太弱了……………………一个略复杂的树形dp敲了俩小时,还tm特别难看……交上去1A让我怀疑这题数据是不是有问题……
其实本来是要做noi2008奥运物流的,然后找到了一个ppt,讲了那类问题的解决办法,这道是个比那个稍简单的思想差不多的题
用dp[i][j][k]表示以i为根的子树中放j个伐木站,并且离i最近的祖先k也放了一个伐木站的最小花费,这里的这个k相当于是一种假设的状态,是一种不错的想法。
然后转移写的超级恶心。。看代码注释吧……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
#define inf 0x3f3f3f3f
using namespace std;
int dp[N][55][N],F[55][N];
int dis[N][N],w[N];
int n,m,f[N];
struct edge{
    int to,next;
}e[N];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
void dfs(int u)
{
    for(int last=u,i=f[u];i!=-1;i=f[i]) 
        dis[u][i]=dis[u][last]+dis[last][i],last=i;
    for(int i=h[u];e[i].to;i=e[i].next) 
        dfs(e[i].to);
}
void tree_dp(int u)
{
    bool flag=1;
    for(int i=h[u];e[i].to;i=e[i].next) flag=0,tree_dp(e[i].to);
///////////////////处理叶子节点……//////////////////////// 
    if(flag)
    {
        for(int i=f[u];i!=-1;i=f[i]) dp[u][0][i]=dis[u][i]*w[u];
        return;
    }
///////////////////当u不建的时候//////////////////////// 
    for(int i=h[u];e[i].to;i=e[i].next)
    {
        int v=e[i].to;
        for(int p=u;p!=-1;p=f[p])
        {
            for(int j=m;j>=0;j--)
            {   
                int tmp=inf;
                for(int k=0;k<=j;k++)
                tmp=min(tmp,dp[u][k][p]+dp[v][j-k][p]);
                dp[u][j][p]=tmp;
            }
        }
    }
    for(int p=u;p!=-1;p=f[p]) 
    for(int i=0;i<=m;i++) 
        dp[u][i][p]+=dis[u][p]*w[u];
///////////////////当u建的时候//////////////////////// 
    memset(F,0,sizeof(F));
    for(int i=h[u];e[i].to;i=e[i].next)
    {
        int v=e[i].to;
        for(int p=u;p!=-1;p=f[p])
        {
            for(int j=m;j>=0;j--)
            {   
                int tmp=inf;
                for(int k=1;k<=j;k++)
                tmp=min(tmp,F[k][p]+dp[v][j-k][u]);
                F[j][p]=tmp;
            }
        }
    }
///////////////////更新最小值/////////////////////// 
    for(int i=0;i<=m;i++)
    for(int j=u;j!=-1;j=f[j]) 
    dp[u][i][j]=min(dp[u][i][j],F[i][j]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&f[i]);
        scanf("%d",&dis[i][f[i]]);
        ae(f[i],i);
    }
    f[0]=-1;dfs(0);
    tree_dp(0);
    cout<<dp[0][m][0]<<endl;
}```