hdu 4003 Find Metal Mineral 树形DP

浏览数：28 / 时间：2015年06月09日

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4003

Humans have discovered a kind of new metal mineral on Mars which are distributed in point‐like with paths connecting each of them which formed a tree. Now Humans launches k robots on Mars to collect them, and due to the unknown reasons, the landing site S of all robots is identified in advanced, in other word, all robot should start their job at point S. Each robot can return to Earth anywhere, and of course they cannot go back to Mars. We have research the information of all paths on Mars, including its two endpoints x, y and energy cost w. To reduce the total energy cost, we should make a optimal plan which cost minimal energy cost.

题意描述：火星上有很多矿山（n<=10000），人们发射k（k<=10）个机器人着陆在火星上的S矿山上，目的就是采取每座矿山上的资源。一些矿山之间相互连接着，从一个矿山到另一个与其相连的矿山要消耗能量，问其最少的消耗能量是多少。

算法分析：树形DP，dp[u][i]定义为以u为根的子树中分配了i个机器人消耗的最少能量，特别的是，dp[u][0]表示为以u为树根的子树中分配了一个机器人并且机器人要在走完这颗子树后要回到u点（就相当于没有给子树分配）的最少消耗能量。

那么我们可以列出式子：dp[u][i]=min（dp[u][i],dp[u][i-j]+dp[v][j]+j*cost）（v为u的相邻节点，w为这条路的能量消耗）。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<map>
 9 #define inf 0x7fffffff
10 using namespace std;
11 const int maxn=10000+10;
12 
13 int n,s,k;
14 int father[maxn],dp[maxn][12];
15 vector<pair<int,int> > G[maxn];
16 
17 void dfs(int u,int f)
18 {
19     father[u]=f;
20     int num=G[u].size();
21     for (int i=0 ;i<num ;i++)
22     {
23         int v=G[u][i].first;
24         int cost=G[u][i].second;
25         if (v==f) continue;
26         dfs(v,u);
27         for (int j=k ;j>=0 ;j--)
28         {
29             dp[u][j] += dp[v][0]+2*cost;
30             for (int q=1 ;q<=j ;q++)
31                 dp[u][j]=min(dp[u][j],dp[u][j-q]+dp[v][q]+q*cost);
32         }
33     }
34 }
35 
36 int main()
37 {
38     while (scanf("%d%d%d",&n,&s,&k)!=EOF)
39     {
40         memset(father,-1,sizeof(father));
41         memset(dp,0,sizeof(dp));
42         for (int i=1 ;i<=n ;i++) G[i].clear();
43         int a,b,c;
44         for (int i=0 ;i<n-1 ;i++)
45         {
46             scanf("%d%d%d",&a,&b,&c);
47             G[a].push_back(make_pair(b,c));
48             G[b].push_back(make_pair(a,c));
49         }
50         dfs(s,-1);
51         printf("%d\n",dp[s][k]);
52     }
53     return 0;
54 }