首页 > 代码库 > 算法笔记_166:算法提高 金属采集(Java)
算法笔记_166:算法提高 金属采集(Java)
目录
1 问题描述
2 解决方案
1 问题描述
人类在火星上发现了一种新的金属!这些金属分布在一些奇怪的地方,不妨叫它节点好了。一些节点之间有道路相连,所有的节点和道路形成了一棵树。一共有 n 个节点,这些节点被编号为 1~n 。人类将 k 个机器人送上了火星,目的是采集这些金属。这些机器人都被送到了一个指定的着落点, S 号节点。每个机器人在着落之后,必须沿着道路行走。当机器人到达一个节点时,它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后,可以从任意一个节点返回地球。当然,回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息,包括它的两个端点 x 和 y,以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属,这个任务就交给你了。
第一行包含三个整数 n, S 和 k ,分别代表节点个数、着落点编号,和机器人个数。
接下来一共 n-1 行,每行描述一条道路。一行含有三个整数 x, y 和 w ,代表在 x 号节点和 y 号节点之间有一条道路,通过需要花费 w 个单位的能量。所有道路都可以双向通行。
1 2 1
2 3 1
2 4 1000
2 5 1000
1 6 1000
所有机器人在 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 的正整数。
2 解决方案
下面代码在蓝桥系统中测评分数为50分,用同样思想版本的C代码测评为100分(PS:具体参考文末参考资料1)。
具体代码如下:
import java.util.ArrayList; import java.util.Scanner; public class Main { public static int n, s, k; public static ArrayList<edge>[] map; public static int[][] dp; static class edge { public int a; public int b; public int v; edge(int a, int b, int v) { this.a = a; this.b = b; this.v = v; } } public void dfs(int start, int father) { for(int i = 0;i < map[start].size();i++) { edge to = map[start].get(i); if(to.b == father) continue; dfs(to.b, start); for(int j = k;j >= 0;j--) { dp[start][j] += dp[to.b][0] + to.v * 2; for(int m = 1;m <= j;m++) { dp[start][j] = Math.min(dp[start][j], dp[start][j - m] + dp[to.b][m] + to.v * m); } } } } @SuppressWarnings("unchecked") public static void main(String[] args) { Main test = new Main(); Scanner in = new Scanner(System.in); n = in.nextInt(); s = in.nextInt(); k = in.nextInt(); map = new ArrayList[n + 1]; dp = new int[n + 1][k + 1]; for(int i = 1;i <= n;i++) map[i] = new ArrayList<edge>(); for(int i = 1;i < n;i++) { int x = in.nextInt(); int y = in.nextInt(); int w = in.nextInt(); map[x].add(new edge(x, y, w)); map[y].add(new edge(y, x, w)); } test.dfs(s, -1); //根节点s处开始DFS遍历,最终回溯的终点就是顶点s System.out.println(dp[s][k]); } }
参考资料:
1.蓝桥杯 算法提高-金属采集
算法笔记_166:算法提高 金属采集(Java)