蓝桥杯 算法提高 金属采集 [ 树形dp 经典 ]

传送门

算法提高 金属采集

时间限制：1.0s   内存限制：256.0MB

   

锦囊1

 

锦囊2

 

锦囊3

 

问题描述

人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 n 个节点，这些节点被编号为 1~n 。人类将 k 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着落点， S 号节点。每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息，包括它的两个端点 x 和 y，以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。

输入格式

第一行包含三个整数 n, S 和 k ，分别代表节点个数、着落点编号，和机器人个数。

接下来一共 n-1 行，每行描述一条道路。一行含有三个整数 x, y 和 w ，代表在 x 号节点和 y 号节点之间有一条道路，通过需要花费 w 个单位的能量。所有道路都可以双向通行。

输出格式

输出一个整数，代表采集所有节点的金属所需要的最少能量。

样例输入

6 1 3 1 2 1 2 3 1 2 4 1000 2 5 1000 1 6 1000

样例输出

3004

样例说明

所有机器人在 1 号节点着陆。

第一个机器人的行走路径为 1->6 ，在 6 号节点返回地球，花费能量为1000。

第二个机器人的行走路径为 1->2->3->2->4 ，在 4 号节点返回地球，花费能量为1003。

第一个机器人的行走路径为 1->2->5 ，在 5 号节点返回地球，花费能量为1001。

数据规模与约定

本题有10个测试点。

对于测试点 1~2 ， n <= 10 ， k <= 5 。

对于测试点 3 ， n <= 100000 ， k = 1 。

对于测试点 4 ， n <= 1000 ， k = 2 。

对于测试点 5~6 ， n <= 1000 ， k <= 10 。

对于测试点 7~10 ， n <= 100000 ， k <= 10 。

道路的能量 w 均为不超过 1000 的正整数。

题解：

思路来自博客：http://www.ylzx8.cn/kaifayuyan/program/192149.html

dp[p][m]:表示在以p为根的子树中停留m个机器人的花费。把一棵子树看作是一个整体。

很好的树形dp，理解了好久。一定注意是要把一棵子数看作一个整体。

一开始，dfs刚到某个节点，如果没有儿子节点的话，那么机器人到此就都可以停了，dp[p][m]为0

如果发现了有一个儿子节点，那么考虑在这个儿子节点停留remain个机器人。

dp[p][k]+=dp[next][0]+cost*2;   //子树son中没有停留机器人，那么意味全反回，最少是去一个所以最少反回一个

for(remain=1;remain<=k;remain++)

dp[p][k]=min(dp[p][k],dp[p][k-remain]+dp[next][remain]+remain*cost);  //注：dfs到第一个儿子的时候，由于暂时没发现其余儿子，所以留在p节点的机器　　　　　　                                                                                                              //  人都不会有多余消耗

随着dfs的深入，每发现一个新儿子，那么更新时就要用考虑到前面所有儿子的状态进行转移。这是一个渐进的过程。

比如，在第二个儿子时，k=1,remain=1 的话，

dp[p][k]=min(dp[p][k],dp[p][k-remain]+dp[next][remain]+remain*cost);

用到的dp[p][k-remain]已经不再是0，因为首先必须把第一个儿子访问过再回到p节点。

所有儿子都dfs过之后，得到的dp[p][m]才不再变化。

518169

[e-mail]

金属采集

04-08 20:17

1.269KB

C++

正确

100

171ms

13.42MB

评测详情

 评测点序号

 评测结果

 得分

 CPU使用

 内存使用

 下载评测数据

  正确 10.00 15ms .949MB 输入 输出
   正确 10.00 0ms .949MB VIP特权
   正确 10.00 140ms .468MB VIP特权
   正确 10.00 0ms .972MB VIP特权
   正确 10.00 0ms .972MB VIP特权
   正确 10.00 0ms .015MB VIP特权
   正确 10.00 156ms .472MB VIP特权
   正确 10.00 171ms .472MB VIP特权
   正确 10.00 171ms .42MB VIP特权
   正确 10.00 171ms .468MB VIP特权 

评测详情

 #include <cstdio>
 #include <cmath>
 #include <vector>
 #include <cstring>

 #define N 100005

 using namespace std;

 int n,s,K;
 int dp[N][];        //dp[p][m]:表示在以p为根的子树中停留m个机器人的花费。把一棵子树看作是一个整体。

 typedef struct
 {
     int to;
     int w;
 }PP;

 vector<PP>bian[N];
 int vis[N];

 void dfs(int p)
 {
     vis[p]=;
     int i;
     int next;
     int cost;
     int k;
     int remain;
     for(i=;i<bian[p].size();i++)
     {
         next=bian[p][i].to;
         if(vis[next]==) continue;
         cost=bian[p][i].w;
         dfs(next);
         for(k=K;k>=;k--){        //这里要注意不能掉了0的情况
             dp[p][k]+=dp[next][]+cost*;        //子树son中没有停留机器人，那么意味全反回，最少是去一个所以最少反回一个
             for(remain=;remain<=k;remain++){        //在子树son中停raim个机器人的情况
                 dp[p][k]=min(dp[p][k],dp[p][k-remain]+dp[next][remain]+remain*cost);
             }
         }
     }
 }

 int main()
 {
     int x,y,w;
     PP te;
     //freopen("data.in","r",stdin);
     memset(dp,,sizeof(dp) );
     memset(vis,,sizeof(vis));
     int i;
     scanf("%d%d%d",&n,&s,&K);
     for(i=;i<=n;i++){
         bian[i].clear();
     }
     for(i=;i<n-;i++){
         scanf("%d%d%d",&x,&y,&w);
         te.w=w;
         te.to=y;
         bian[x].push_back(te);
         te.to=x;
         bian[y].push_back(te);
     }
 //    printf("sdf a\n");
     dfs(s);
     printf("%d\n",dp[s][K]);
     return ;
 }