hdoj4003 (树形dp+分组背包)

题目链接：https://vjudge.net/problem/HDU-4003

题意：给一棵边权树，在树根s有m个人，要通过m个人遍历到所有点，一个人经过一条边花费为边的权值，求最小花费（可以走已经走过的边）。

思路：

　　状态比较好想，用dp[u][j]表示在u结点的子树中有j个人的最小花费。但转移方程有点难想。

　　重要的是怎么处理dp[u][0]，对dp[v][0]，即在v结点的子树中有0个人的最小花费，那么只能通过v的父结点u过来机器人，假设来x个人，那这x个人在遍历v子树所有点之后还要回到u才行，那么花费为2*sum[v]+2k*w，sum[v]是v子树中所有边的权值和，w是u->v的边权，所以k=1时花费最小，花费为2*sum[v]+2*w。故dp[u][0]=sum(2*sum[v],2*w)，外面的sum表示求和。

　　j>0时，可以简单地推出：dp[u][j]=min(dp[u][j] , dp[u][j-k]+dp[v][k]+k*w)，v是u的子结点，k表示子结点v有k个人，w是u->v的边权。

AC代码：

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=1e4+;

const int inf=0x3f3f3f3f;

int n,s,m,cnt,head[maxn],sum[maxn],dp[maxn][];

struct node{

    int v,w,nex;

}edge[maxn<<];

void adde(int u,int v,int w){

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void dfs(int u,int fa){

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        if(v==fa) continue;

        dfs(v,u);

        for(int j=m;j>=;--j)

            for(int k=;k<=j;++k)

                if(k) dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+k*edge[i].w);

                else dp[u][j]+=dp[v][]+*edge[i].w;

    }

}

int main(){

    while(~scanf("%d%d%d",&n,&s,&m)){

        cnt=;

        for(int i=;i<=n;++i){

            head[i]=;

            for(int j=;j<=m;++j)

                dp[i][j]=;

        }

        for(int i=;i<n;++i){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            adde(u,v,w);

            adde(v,u,w);

        }

        dfs(s,);

        printf("%d\n",dp[s][m]);

    }

    return ;

}

巴特西

hdoj4003 (树形dp+分组背包)

最新文章

热门文章