最小生成树:在 无向带权图 中选择一些边，在保证连通性的情况下，边的总权值最小
最小生成树可能不只一棵，只要保证边的总权值最小，就是正确的最小生成树。
如果无向带权图有n个点，那么最小生成树一定有n-1条边

Kruskal算法(最常用)
1 把所有的边，根据权值从小到大排序，从权值小的边开始考虑
2 如果连接当前的边不会形成环，就选择
3 如果连接当前的边会形成环，就不选
4 考察完所有的边，就得到最小生成树

用并查集来判断会不会形成环

P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例 #1

输入 #1

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

输出 #1

1
7

说明/提示

数据规模：

对于 $20%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Kruskal算法模版（洛谷）
// 静态空间实现
// 这是输入输出处理效率很高的写法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

// 时间复杂度O(m * log m) + O(n + m)
public class Main {

	public static int MAXN = 5001;

	public static int MAXM = 200001;

	public static int[] father = new int[MAXN];

	// u, v, w
	public static int[][] edges = new int[MAXM][3];

	public static int n, m;

	public static void build() {
		for (int i = 1; i <= n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	// 如果x和y本来就是一个集合，返回false
	// 如果x和y不是一个集合，合并之后返回true
	public static boolean union(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) {
			father[fx] = fy;
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			build();
			for (int i = 0; i < m; i++) {
				in.nextToken();
				edges[i][0] = (int) in.nval;
				in.nextToken();
				edges[i][1] = (int) in.nval;
				in.nextToken();
				edges[i][2] = (int) in.nval;
			}
			Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);
			int ans = 0;
			int edgeCnt = 0;
			for (int[] edge : edges) {
				if (union(edge[0], edge[1])) {
					edgeCnt++;
					ans += edge[2];
				}
			}
			out.println(edgeCnt == n - 1 ? ans : "orz");
		}
		out.flush();
		out.close();
		br.close();
	}

}

时间复杂度O(m*logm)+O(n)+O(m)

Prim算法(不常用)