蓝桥杯-算法提高 金属采集

问题描述

人类在火星上发现了一种新的金属!这些金属分布在一些奇怪的地方,不妨叫它节点好了。一些节点之间有道路相连,所有的节点和道路形成了一棵树。一共有 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 的正整数。

解题思路

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

[k-remain]+dp[next][remain]+remain*cost);

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

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

参考代码

此处为隐藏的内容!
发表评论并刷新,才能查看
俊霖

发表评论

您必须

目前评论:4   其中:访客  3   博主  1

  1. ymx200181 5

    好难

  2. 俊霖 俊霖

    这道题本来是没有注释的,一个妹子说看不懂,我才写的注释。

  3. QB20D4A99E3BCB0609A7A245A026F7AAA 1

    学习

  4. zhang7324199 0

    来吧 看看