蓝桥杯-通电(最小天生树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方法，去利用输入样例手动求解两点之间的权重。
代码

2. import java.util.ArrayList;
3. import java.util.Comparator;
4. import java.util.Scanner;
5. public class 通电 {
6.     static int []root;
7.     static int g[][];
8.     public static void main(String[] args) {
9.         Scanner sc = new Scanner(System.in);
10.         int n = sc.nextInt();
11.         root = new int[n + 1];
12.         for(int i = 1;i <= n;i ++) {
13.             root[i] = i;
14.         }
15.         g = new int[n+1][3];
16.         ArrayList<Edge> list = new ArrayList<>();
17.         for(int i = 1;i <= n;i ++) {
18.             int x = sc.nextInt();
19.             int y = sc.nextInt();
20.             int h = sc.nextInt();
21.             g[i][0] = x;
22.             g[i][1] = y;
23.             g[i][2] = h;
24.             for(int j = 1;j < i;j ++) {
25.                 list.add(new Edge(i,j,dist(i,j)));
26.             }
27.         }
28.         list.sort(Comparator.comparing((Edge e) -> e.w));
29.         double ans = 0;
30.         int cnt = 0;
31.         for(Edge e : list) {
32.             if (find(e.u) != find(e.v)) {
33.                 union(e.u,e.v);
34.                 ans += e.w;
35.                 cnt ++;
36.             }
37.             if (cnt == n - 1) {
38.                 break;
39.             }
40.         }
41.         System.out.printf("%.2f",ans);
42.     }
43.     public static int find(int x) {
44.         if (x != root[x]) {
45.             root[x] = find(root[x]);
46.         }
47.         return root[x];
48.     }
49.     public static boolean union(int x, int y) {
50.         int fx = find(x);
51.         int fy = find(y);
52.         if (fx != fy) {
53.             root[fx] = fy;
54.             return true;
55.         }
56.         else {
57.             return false;
58.         }
59.     }
60.     public static double dist(int i,int j) {
61.         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]);
62.     }
63. }
64. class Edge{
65.     int u, v;
66.     double w;
67.     public Edge (int u, int v, double w) {
68.         this.u = u;
69.         this.v = v;
70.         this.w = w;
71.     }
72. }

复制代码