<span>HDU4003 Find Metal Mineral（树形dp）</span>
题意：
求K个机器人从同一点出发，遍历所有点所需的最小花费
n为节点数，s为起始位置，k为机器人的数量
思路：
dp[i][j]表示以节点i为根节点，消耗j个机器人遍历的最小花费
特别的dp[i][0]表示用一个机器人遍历再返回上层所需要的花费
/* *********************************************** Author :devil Created Time :2016/3/24 10:59:25 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; #define N 10010 int n,s,k,dp[N][11],r,head[N]; struct wq { int v,cost,next; }eg[N*2]; void init() { r=0; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); } void add(int u,int v,int cost) { eg[r].v=v; eg[r].cost=cost; eg[r].next=head[u]; head[u]=r++; eg[r].v=u; eg[r].cost=cost; eg[r].next=head[v]; head[v]=r++; } void dfs(int u,int fa) { for(int i=head[u];i!=-1;i=eg[i].next) { int to=eg[i].v; if(to==fa) continue; for(int j=k;j>=0;j--) { dp[u][j]=dp[u][j]+dp[to][0]+eg[i].cost*2; for(int p=1;p<=j;p++) dp[u][j]=min(dp[u][j],dp[u][j-p]+dp[to][p]+eg[i].cost*p); } } } int main() { //freopen("in.txt","r",stdin); int x,y,z; while(~scanf("%d%d%d",&n,&s,&k)) { init(); for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } dfs(s,-1); printf("%d\n",dp[s][k]); } return 0; }
查看8道真题和解析
