思路

  1. 将所有边按权重从小到大排序 O(mlogm)
  2. 枚举每条边 a->b 权重为c O(m)

如果这条边两端的点不在一个集合内，将他们两所在集合合并。
证明：
假设不选当a前边得到最终的生成树。然后将这条边加上，必然会出现一个环，在这个环上一定可以找出一条长度不小于当前边的边b，用a替换b结果一定不会更差

模板

859. Kruskal算法求最小生成树
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
1≤n≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过 1000。
输入样例：

  1. 4 5
  2. 1 2 1
  3. 1 3 2
  4. 1 4 3
  5. 2 3 2
  6. 3 4 4

输出样例：

  1. 6

代码：

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 100010, M = N * 2;
  5.     static int[][] edges = new int[M][3];
  6.     static int[] fa = new int[N];
  7.     static int n, m;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         n = sc.nextInt();
  11.         m = sc.nextInt();
  13.         for (int i = 0; i <= n; i++)
  14.             fa[i] = i;
  15.         for (int i = 0; i < m; i++) {
  16.             edges[i][0] = sc.nextInt();
  17.             edges[i][1] = sc.nextInt();
  18.             edges[i][2] = sc.nextInt();
  19.         }
  21.         Arrays.sort(edges, (o1, o2) -> (o1[2] - o2[2]));
  22.         int sum = 0, cnt = 0;
  23.         for (int[] e : edges) {
  24.             int a = e[0], b = e[1], c = e[2];
  25.             if (merge(a, b)) {
  26.                 cnt++;
  27.                 sum += c;
  28.             }
  29.         }
  31.         if (cnt == n - 1)
  32.             System.out.println(sum);
  33.         else
  34.             System.out.println("impossible");
  35.     }
  37.     static boolean merge(int x, int y) {
  38.         int px = find(x), py = find(y);
  39.         if (px != py) {
  40.             fa[px] = py;
  41.             return true;
  42.         }
  43.         return false;
  44.     }
  46.     static int find(int x) {
  47.         return x == fa[x] ? x : (fa[x] = find(fa[x]));
  48.     }
  49. }