首页 > 代码库 > hdu4003（树形dp）
hdu4003（树形dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4003
题意：给定一棵n个节点的树，遍历每条数边都需要费用cost，现在给定k个机器人，要求用这个k个机器人遍历整棵树，使得经过的费用和最小，n<=10000.
分析：dp[u][j]表示有j个机器人不回来的最小值，dp[u][0]表示有一个机器人回来的最小值，即没有一个机器停留在那颗子树上。至于为甚么只考虑一个机器人回来的原因是同时派多个机器人下去，如果回来的人越多，走重复路线会越多，耗费越多。
这里的树形dp和以往有点不同，原本树形dp对于每个根节点u的儿子v相当于分组背包里的一组，对于每组里的物品（v的儿子）至多取一个进行dp，这里因为要遍历完所有边，所以对于每组的物品必须取一个。
总而言之，假设根节点u有x个子节点，dp[u][j]=min（dp[v1][num1]+dp[v2][num2]+...+dp[vx][numx]）
如何分配numk（0<=numk<=j）让num1+num2+...+numx=j使得dp[u][j]值最小。这里对于每个子节点numk枚举0~j枚举一遍就好。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010#define FILL(a,b) (memset(a,b,sizeof(a)))using namespace std;struct edge{ int v,w,next; edge(){} edge(int v,int w,int next):v(v),w(w),next(next){}}e[2*N];int head[N],tot,n,m,s;int dp[N][15];int a[N][15],b[N][15];void addedge(int u,int v,int w){ e[tot]=edge(v,w,head[u]); head[u]=tot++;}void dfs(int u,int fa){ for(int i=head[u];~i;i=e[i].next) { int v=e[i].v,w=e[i].w; if(v==fa)continue; dfs(v,u); for(int j=m;j>=1;j--) { dp[u][j]+=dp[v][0]+2*w;//派一个人下去遍历完后再回来，保证选了一个 for(int k=1;k<=j;k++)//枚举派多个下去，选出最优值 dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+w*k); } dp[u][0]+=dp[v][0]+2*w; }}int main(){ int u,v,w,sum; while(scanf("%d%d%d",&n,&s,&m)>0) { FILL(head,-1);FILL(dp,0); FILL(a,0);FILL(b,0);tot=0; for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs(s,-1); printf("%d\n",dp[s][m]); }}
hdu4003（树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。