HDU 4003:Find Metal Mineral 树形DP+分组背包 Find Metal Mineral
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4003
题意：
有一棵树（存在N个节点），树上每条边都有权值，在其根节点S上有K个机器人，求这些机器人遍历所有点所花费的最小权值和
题解：
设dp[i][j]为以i为根节点的子树上有X个机器人的最小花费，按分组背包的思想跑一遍DP就好了，注意每个节点上j为0的情况
代码
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int maxn=10001;
int dp[maxn][11];//以i为根节点的子树上有X个机器人的最小花费
bool mark[maxn];
int mmin(int x,int y)
{
return x<y?x:y;
}
int mmax(int x,int y)
{
return x>y?x:y;
}
struct node
{
int to,cost;
node(int x=0,int y=0)
{
to=x,cost=y;
}
};
vector<node>q[maxn];
int m,sum[maxn];
void Dfs(int id)
{
mark[id]=true;
for(int i=0;i<q[id].size();++i)
{
int v=q[id][i].to;
if(mark[v])continue;
int cost=q[id][i].cost;
Dfs(v);
for(int j=m;j>=1;--j)
{
dp[id][j]+=cost*2+dp[v][0];
for(int k=0;k<=j;++k)
{
if(k)dp[id][j]=mmin(dp[id][j],dp[id][j-k]+dp[v][k]+cost*k);
else dp[id][j]=mmin(dp[id][j],dp[id][j-k]+dp[v][k]+cost*2);//k为0需要往回跑
}
}
dp[id][0]+=cost*2+dp[v][0];
}
}
int main()
{
int N,S,K,a,b,c;
while(~scanf("%d%d%d",&N,&S,&K))
{
m=K;
for(int i=1;i<=N;++i)
q[i].clear();
memset(dp,0,sizeof(dp));
memset(mark,false,sizeof(mark));
for(int i=1;i<N;++i)
{
scanf("%d%d%d",&a,&b,&c);
q[a].push_back(node(b,c));
q[b].push_back(node(a,c));
}
Dfs(S);
printf("%d
",dp[S][K]);
}
}