蓝桥杯：通电

蓝桥杯： 通电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≤1000，0≤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[n+5];for(int i = 1;i<=n;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);//建立一个列表存放村庄信息List<Point> list = new ArrayList<>();for(int i = 1;i<=n;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了一个小时.....PriorityQueue<Edge> pq = new PriorityQueue<>((e1,e2)->((Double.compare(e1.price,e2.price))));for(int i = 1;i<n;i++){//编号为i的村庄存放在列表的i-1处Point self = list.get(i-1);for(int j = i+1;j<=n;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(x+y) + h; //对x+y开根号 + 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);}
}