最小生成树(MST),顾名思义,对于带权无向连通图 GG ,其所有生成树中的权值和最小者 TT ,是其最小生成树。

模板题

题目

洛谷 P3366 | 【模板】最小生成树

题目描述

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

输入格式

第一行包含两个整数 N,MN,M ,表示该图共有 NN 个结点和 MM 条无向边。 接下来 MM 行每行包含三个整数 Xi,Yi,ZiX_i,Y_i,Z_i​ ,表示有一条长度为 ZiZ_i​ 的无向边连接结点 Xi,YiX_i,Y_i ​ 。

输出格式

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

输入输出样例

输入
1
2
3
4
5
6
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出
1
7

说明/提示

数据规模:

对于 20%20\% 的数据, N5N\le 5M20M\le 20

对于 40%40\% 的数据, N50N\le 50M2500M\le 2500

对于 70%70\% 的数据, N500N\le 500M104M\le 10^4

对于 100%100\% 的数据: 1N50001\le N\le 50001M2×1051\le M\le 2\times 10^51Zi1041\le Z_i \le 10^4 .

样例解释:

2259.png

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

Kruscal 算法

思路

Kruscal 算法是求 MST 的一种比较简单的方法,其核心思想是用贪心的思想构造 MST。

考虑图 GG 中权值最小的边 e1e_1 ,它一定在 MST 中。选中 e1e_1 后,次小的边 e2e_2 ,它在 MST 中与 e1e_1 在 MST 中不矛盾。以此类推,每次我们都考虑将未选边集中权值最小的边 eie_i 加入 MST。

然而不是所有这样的边都能加入 MST,因为 MST 毕竟还是一棵树,即无圈连通图,因此若 eie_i 连结的两个顶点 u,vu, v 已经包含在已选边集的生成子图中,则 eie_i 不能加入 MST。如此往复,直到加入 n1n-1 条边,MST 构造完成。

为什么这样是正确的呢?我们注意到上述过程的的关键点是对于 eie_i ,如果 eie_i 连结的两个顶点 u,vu, v 已经包含在已选边集的生成子图中,则 eie_i 不加入 MST,其他部分都显然正确。只需要探讨不合法 eie_i 不加入的正确性即可。

对于 eie_i ,如果 eie_i 不合法,我们却想让它成为 MST 的一条边,则只需要将 eie_i 之前的某条边从 MST 中去掉即可,假设其为 eje_j ,但是显然 eie_i 的权值 \ge eje_j ,结果会更差。故 eie_i 应该去掉。

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 5050;
const int maxm = 200500;
int n, m, ans;
int fa[maxn];
class Node
{
public:
int u, v, w;
bool operator<(const Node &b) const
{
return w < b.w;
}

} E[maxm];

int getfa(int x)
{
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

bool check(int x, int y)
{
return getfa(x) == getfa(y);
}

void union_(int x, int y)
{
fa[getfa(x)] = getfa(y);
}

int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
E[i].u = u;
E[i].v = v;
E[i].w = w;
}
sort(E + 1, E + m + 1);
for (int i = 1; i <= m; i++)
{
if (check(E[i].u, E[i].v))
continue;
ans += E[i].w;
union_(E[i].u, E[i].v);
}
for (int i = 2; i <= n; i++)
{
if (getfa(i) != getfa(1))
{
printf("orz");
return 0;
}
}
printf("%d", ans);
return 0;
}

解释

为事先上述算法,我们需要先将边从小到大排序,每次检测 eie_i 两端的点 u,vu, v 在不在已选边集对应的点集内:如果不在,则将 uuvv 加入该点集;如果在,则跳过这条边。检测点集的过程可以用并查集实现。

Prim 算法

思路

代码

1