苏州知名网站建设建站公司,网站子目录安装dedecms导致网页布局混乱的解决方法,帝国企业网站模板,05网数学书答案蓝桥杯#xff1a; 通电https://www.lanqiao.cn/problems/162/learning/
目录
题目描述
输入描述
输出描述
输入输出样例
输入
输出
题目分析(最小生成树)#xff1a; AC代码(Java) 题目描述 2015 年#xff0c;全中国实现了户户通电。作为一名电力建设者#xff0…蓝桥杯 通电https://www.lanqiao.cn/problems/162/learning/
目录
题目描述
输入描述
输出描述
输入输出样例
输入
输出
题目分析(最小生成树) AC代码(Java) 题目描述 2015 年全中国实现了户户通电。作为一名电力建设者小明正在帮助一带一路上的国家通电。 这一次小明要帮助 n 个村庄通电其中 1 号村庄正好可以建立一个发电站所发的电足够所有村庄使用。 现在这 n 个村庄之间都没有电线相连小明主要要做的是架设电线连接这些村庄使得所有村庄都直接或间接的与发电站相通。 小明测量了所有村庄的位置坐标和高度如果要连接两个村庄小明需要花费两个村庄之间的坐标距离加上高度差的平方形式化描述为坐标为(x1,y1) 高度为 ℎ1 的村庄与坐标为 (x2,y2) 高度为 ℎ2 的村庄之间连接的费用为 高度的计算方式与横纵坐标的计算方式不同。 由于经费有限请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
输入描述 输入的第一行包含一个整数 n 表示村庄的数量。 接下来 n 行每个三个整数 x,y,h分别表示一个村庄的横、纵坐标和高度其中第一个村庄可以建立发电站。 其中1≤n≤10000≤x,y,h≤10000。
输出描述 输出一行包含一个实数四舍五入保留 2 位小数表示答案。
输入输出样例 输入
4
1 1 3
9 9 7
8 8 6
4 5 4 输出
17.41 题目分析(最小生成树) 把村庄看成顶点求每个村庄之间搭建电线的花费最少也就是每个顶点直接相连所需要的花费最少很明显是考最小生成树。 如果不了解最小生成树可以先看蓝桥杯聪明的猴子。这个题是最小生成树的模板题。 题目有个附加条件就是1号村庄是有发电站的并且其他村庄想要有电要么直接从1号村庄建立电线要么和已经与1号村庄建立电线的村庄来建立电线如 假如2号村庄已经同1号村庄架设了电线那么此时1号村庄和2号村庄都是通电的也就是说3号村庄与1号村庄、2号村庄搭设电线他都能通电因此我们只需要根据最小生成树的贪心策略每次选择花费最小的一条边进行连接即可完成所有村庄的通电。 因为最小生成树是用最小花费建立一个连接所有顶点的图那么也就是1号村庄是肯定会被连接的我们不需要对1号村庄进行特殊处理直接套用最小生成树的模板即可(因此本题也是一个最小生成树的模板题)。 PS注意建立边的花费是浮点数。 AC代码(Java) 在写优先队列的升序排序的时候记得题目中的代价也可以叫做建立边的花费这里用price来表示是浮点数的所以要用对应的包装类的比较方法compare(),我当成整型来处理写成了(int)e1.price-e2.price,最后一个用例没过。 应该是用Double的compare方法来比较两个price。
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//并查集模板static int[] pre;public static void initPre(int n){pre new int[n5];for(int i 1;in;i)pre[i] i;}public static int find(int x) {if(pre[x] x) return x;return pre[x] find(pre[x]);}public static void join(int a,int b) {pre[find(a)] pre[find(b)];}//存储村庄的坐标信息static class Point{int id; //村庄编号唯一标识int x; //x轴int y; //y轴int h; //高public Point(int id,int x,int y,int h) {this.id id;this.x x;this.y y;this.h h;}}//两个村庄之间建立边static class Edge{//self和target建立边架设电线Point self;Point target;double price; //建立边的花费public Edge(Point self,Point target,double price) {this.self self;this.target target;this.price price;}}public static void main(String[] args) {Scanner scan new Scanner(System.in);int n scan.nextInt(); //村庄编号initPre(n);//建立一个列表存放村庄信息ListPoint list new ArrayList();for(int i 1;in;i){int x scan.nextInt();int y scan.nextInt();int h scan.nextInt();list.add(new Point(i,x,y,h));}scan.close();//将所有村庄之间架设电线建边的信息存放到优先队列之中按照升序排序//(PS:这里使用Double的compare来比较大小如果直接用(int)e1.price-e2.price,将比较结果转换成(int)最后一个用例有错),Debug了一个小时.....PriorityQueueEdge pq new PriorityQueue((e1,e2)-((Double.compare(e1.price,e2.price))));for(int i 1;in;i){//编号为i的村庄存放在列表的i-1处Point self list.get(i-1);for(int j i1;jn;j){Point target list.get(j-1);//计算他们之间的花费double x Math.pow(self.x-target.x,2); //(x1-x2)^2double y Math.pow(self.y-target.y,2); //(y1-y2)^2double h Math.pow(self.h-target.h,2); //(h1-h2)^2double price Math.sqrt(xy) h; //对xy开根号 h//放入优先队列之中pq.add(new Edge(self,target,price));}}//收集完全部边的信息之后每次取出花费最小的一条边建立边int e 0; //对于一个顶点为n的图最短路径应该是n-1条边double ans 0;while(!pq.isEmpty()) {Edge edge pq.poll();Point self edge.self;Point target edge.target;//判断建立这条边是否会产生环如果会就跳过if(find(self.id) find(target.id)) {continue;}//如果不会产生环那么就建立这条边同时记录花费join(self.id,target.id);ans edge.price;e;if(e n-1) break;}//格式化输出保留两位小数System.out.printf(%.2f,ans);}
}
