2011-0057

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

= 题目大意 =
有一颗有N个节点的无向树，每个节点有一个价值Vi，表示有Vi价值的宝物在这个节点（只能取一次），同时每条边有一个长度Li，表示走这条边需要Li天。给定某个点X，求在Mi天回到X的前提下能获取的最大宝物价值。

= 解题报告 =
这题是一个简单的树形动态规划，设Dp[i][j]表示在第i个节点并且已经过了j天的最大宝物获得量，那么假设我们现在处理到第i个节点，并且他的子节点全部处理过了，那么就相当于所有子节点有一个价值（Dp[i.son][k]），有一个重量（k），这就是个经典的0/1背包问题，也就是一个经典的树上背包的动态规划，当然似乎转化为左儿子右兄弟也可以做？总而言之就是这样。最后遍历一下所有Dp[X][i]找到最大值即可。

= 题目代码 =
{{{
#include<cstdio>
#include<cstring>
#define MAXN 1005
#define MAXD 2005

struct EdgeType{
    int adj,t;
    EdgeType *next;
}Edge[MAXN*10],*Gr[MAXN];

int n,m,root,dp[MAXN][MAXD],e,v[MAXN];
//bool mark[MAXN];

int InsertEdge(int x,int y,int z){
    Edge[++e].adj=y;
    Edge[e].t=z;
    Edge[e].next=Gr[x];
    Gr[x]=&Edge[e];
    return 0;
}

int Dfs(int now,int pre){
    int nowt,j,k;
    dp[now][0]=v[now];

    for(EdgeType *t=Gr[now];t;t=t->next){
        if(t->adj!=pre){
            Dfs(t->adj,now);
            nowt=t->t;
            for(k=m;k>=0;k--)
                for(j=0;j<=m;j++)
                    if(k-j-nowt*2>=0)
                        if(dp[now][k]<dp[t->adj][j]+dp[now][k-j-nowt*2])
                            dp[now][k]=dp[t->adj][j]+dp[now][k-j-nowt*2];
        }
    }

    return 0;
}

int main(){
    int i,j,bestans,x,y,z;
    while(scanf("%d",&n)!=EOF){
        memset(Edge,0,sizeof(Edge));
        memset(Gr,0,sizeof(Gr));
        e=0;
        for(i=1;i<=n;i++)scanf("%d",&v[i]);
        for(i=1;i<=n-1;i++){
            scanf("%d%d%d",&x,&y,&z);
            InsertEdge(x,y,z);
            InsertEdge(y,x,z);
        }
        scanf("%d%d",&root,&m);
        memset(dp,0,sizeof(dp));
        //memset(tp,0,sizeof(tp));
        //memset(Dis,0,sizeof(Dis));
        //memset(mark,0,sizeof(mark));
        //GetDis(root,0);
        Dfs(root,0);
        bestans=0;
        for(j=0;j<=m;j++)
            if(dp[root][j]>bestans)bestans=dp[root][j];
        printf("%d\n",bestans);
    }
}
}}}

Finished by Dai@NeverLand

题目大意

有一颗有N个节点的无向树，每个节点有一个价值Vi，表示有Vi价值的宝物在这个节点（只能取一次），同时每条边有一个长度Li，表示走这条边需要Li天。给定某个点X，求在Mi天回到X的前提下能获取的最大宝物价值。

解题报告

这题是一个简单的树形动态规划，设Dp[i][j]表示在第i个节点并且已经过了j天的最大宝物获得量，那么假设我们现在处理到第i个节点，并且他的子节点全部处理过了，那么就相当于所有子节点有一个价值（Dp[i.son][k]），有一个重量（k），这就是个经典的0/1背包问题，也就是一个经典的树上背包的动态规划，当然似乎转化为左儿子右兄弟也可以做？总而言之就是这样。最后遍历一下所有Dp[X][i]找到最大值即可。

题目代码

#include<cstdio>
#include<cstring>
#define MAXN 1005
#define MAXD 2005
struct EdgeType{
    int adj,t;
    EdgeType *next;
}Edge[MAXN*10],*Gr[MAXN];
int n,m,root,dp[MAXN][MAXD],e,v[MAXN];
//bool mark[MAXN];
int InsertEdge(int x,int y,int z){
    Edge[++e].adj=y;
    Edge[e].t=z;
    Edge[e].next=Gr[x];
    Gr[x]=&Edge[e];
    return 0;
}
int Dfs(int now,int pre){
    int nowt,j,k;
    dp[now][0]=v[now];
    for(EdgeType *t=Gr[now];t;t=t->next){
        if(t->adj!=pre){
            Dfs(t->adj,now);
            nowt=t->t;
            for(k=m;k>=0;k--)
                for(j=0;j<=m;j++)
                    if(k-j-nowt*2>=0)
                        if(dp[now][k]<dp[t->adj][j]+dp[now][k-j-nowt*2])
                            dp[now][k]=dp[t->adj][j]+dp[now][k-j-nowt*2];
        }
    }
    return 0;
}
int main(){
    int i,j,bestans,x,y,z;
    while(scanf("%d",&n)!=EOF){
        memset(Edge,0,sizeof(Edge));
        memset(Gr,0,sizeof(Gr));
        e=0;
        for(i=1;i<=n;i++)scanf("%d",&v[i]);
        for(i=1;i<=n-1;i++){
            scanf("%d%d%d",&x,&y,&z);
            InsertEdge(x,y,z);
            InsertEdge(y,x,z);
        }
        scanf("%d%d",&root,&m);
        memset(dp,0,sizeof(dp));
        //memset(tp,0,sizeof(tp));
        //memset(Dis,0,sizeof(Dis));
        //memset(mark,0,sizeof(mark));
        //GetDis(root,0);
        Dfs(root,0);
        bestans=0;
        for(j=0;j<=m;j++)
            if(dp[root][j]>bestans)bestans=dp[root][j];
        printf("%d\n",bestans);
    }
}

Finished by Dai@NeverLand