最小生成树

AisDaeun 7 2023-10-29

考虑这样一个问题:对于连通无向图G = (V, E),若存在T \subseteq E(V, T)为树,使得\sum\limits_{e \in E} e.w最小,则称T为G的最小生成树(Minimum Spaning Tree, MST)。

形象理解,就是对于一张图,用权值之和最小的边集连通所有的点,且这个边集是一棵树,也就是说不能有环。

主要有两种方法求出T:Kruskal算法和Prim算法,分别是对边和点进行贪心。

模板题:洛谷P3366

Krukal算法

一张图中权值最小的边一定在MST中,因此全局最优解满足局部最优解,只需要把边按权值从小到大排序,再加边即可。剩下的问题就是保证图中没有环。

用并查集实现比较优雅。加边时,把边的两个端点合并,如果这两个端点在合并之前就属于同一集合,说明加了这条边之后会出现环。此时跳过该边即可。

算法时间复杂度:①排序复杂度O(m \log m);②加边复杂度O(m)。所以,Kruskal算法的复杂度为O(m \log m)

#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 2e5 + 10;
struct edge {int u, v, w; } e[M];
int n, m;
int fa[N];
int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
void kruskal() {
	sort(e + 1, e + m + 1, [] (edge &a, edge &b) {return a.w < b.w; });
	for (int i = 1; i <= n; i++) fa[i] = i;
	int ans = 0, cnt = 0;
	for (int i = 1; i <= m; i++) {
		if (cnt == n - 1) break;
		int x = get(e[i].u), y = get(e[i].v);
		if (x == y) continue;
		ans += e[i].w;	
		fa[x] = y;
		cnt++;
	} 
	if (cnt == n - 1) printf(""%d\n"", ans);
	else puts(""orz"");
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) 
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	kruskal();
	return 0;
}

Prim算法