蓝桥杯-通电(最小生成树java)

题目

思路

        这道题其实也挺容易看出来是最小生成树的。我当时做的时候确实是能看出来是考的最小生成树，union()，find()那些方法我也能写出来，但是，我完全不知道怎么去利用给你的输入数据，去求解题目，也就是知道这个算法，也会写这个算法板子，但是不会做题T_T。

        先来讲一下具体的题意，就是有n个村庄，其中1号村庄是发电站，让你给这些村庄之间添加电线，使得它们相互连接，使得它们直接或间接的与发电站相通。但是加电线是需要费用的，问你如何添加电线，让电线花费最少且使得这n个村庄都通电。

        这就可以转化成，n个节点，然后你从它们产生的边里，选择前n-1个权值最小的边，使得这n个节点能够相互到达。其实题中的这个1号村庄你放哪都无所谓，只要n个节点是连通的，他那个电就能给你传通过去。所以就很明显，就是最小生成树算法。我目前只会Kruskal，所以该题使用Kruskal求解的。

        这里记录为什么自己做的时候即使知道了算法，也没有把题目做出来。最开始我读完输入数据的时候，我打算用两层for循环，暴力的去计算任意两个节点之间的费用，然后把费用存到list列表里边。但是当时做的时候，我无法保证list里的前n-1个权重所在的边它们不构成环，也就是我无法保证它们能够使得n个村庄成为一个最小生成树。然后，就没写下去T_T。

        后来看了大佬们的题解，发现他们有的也是用两层循环去求费用的，只不过他们的更加的巧妙。直接又建了一个Edge类，然后里边有边的起点、终点、权重以及初始化。建类有一个什么好处呢，就是你这时初始化list列表时，你里边的泛型就能写成Edge，然后你每计算两个村庄之间的费用，你就可以new一条Edge，把起点u，终点v以及权重w同时赋值给你刚new完的Edge对象，然后加到list里边就好了。

        其实这道题，相对于前一篇文章的电动车，只不过拐了一个弯，需要你主动地去求一下边的权重，然后以一种合适的方式，把u、v、w存起来，就像电动车的输入样例一样。这样也就转换成电动车那题的模式了，后边就正常的使用Kruskal算法就可以。

        下面代码中的两层for循环那，j < i我的理解就是，他只算了矩阵的下三角，因为对称矩阵嘛。相对于电动车那题绕了的弯子就是额外加了一个dist方法，去利用输入样例手动求解两点之间的权重。

代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;
public class 通电 {static int []root;static int g[][];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();root = new int[n + 1];for(int i = 1;i <= n;i ++) {root[i] = i;}g = new int[n+1][3];ArrayList<Edge> list = new ArrayList<>();for(int i = 1;i <= n;i ++) {int x = sc.nextInt();int y = sc.nextInt();int h = sc.nextInt();g[i][0] = x;g[i][1] = y;g[i][2] = h;for(int j = 1;j < i;j ++) {list.add(new Edge(i,j,dist(i,j)));}}list.sort(Comparator.comparing((Edge e) -> e.w));double ans = 0;int cnt = 0;for(Edge e : list) {if (find(e.u) != find(e.v)) {union(e.u,e.v);ans += e.w;cnt ++;}if (cnt == n - 1) {break;}}System.out.printf("%.2f",ans);}public static int find(int x) {if (x != root[x]) {root[x] = find(root[x]);}return root[x];}public static boolean union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {root[fx] = fy;return true;}else {return false;}}public static double dist(int i,int j) {return Math.sqrt((g[i][0]-g[j][0])*(g[i][0]-g[j][0]) + (g[i][1]-g[j][1])*(g[i][1]-g[j][1])) + (g[i][2]-g[j][2])*(g[i][2]-g[j][2]);}
}
class Edge{int u, v;double w;public Edge (int u, int v, double w) {this.u = u;this.v = v;this.w = w;}
}