最小生成树

前言

最小生成树是图论的一种，生成树问题研究的就是把图里面所有顶点保留，但只会选择部分边所得到的树。

分析

P3366 【模板】最小生成树

\(\text{Kruscal 算法}\)

\(\text{Kruscal}\) 是利用并查集实现的算法，适合用于稀疏图，它的时间复杂度为 \(O(m\log m)\)（\(m\) 为边数），具体实现过程如下：

1. 将所有边从小到大排序；
2. 每个点分配并查集；
3. 选择未使用的边中的边权最小的，如果这条边连接的两个点已未联通，合并并查集；
4. 不断去选择，直到所有点均被使用或者未使用的点没有任何连边。

\(\text{Prim 算法}\)

这种算法时间复杂度不如 \(\text{Kruscal}\) 优秀，仅有 \(O(n^2 + m)\)，只有加上堆优化才能拥有较优秀的复杂度，为 \(O(m \log m)\)，它的具体实现方式与最短路中 \(\text{Dijkstra}\) 相同，感兴趣的读者可以尝试自己去实现。其实是不想写这玩意。

Code

那么，现在给出 \(\text{Kruscal}\) 的代码。
AC Code of P3366 【模板】最小生成树

#include <bits/stdc++.h>

#define int long long
//#pragma G++ optimize(2) 

using namespace std;

const int N = 2e5 + 10;

int n,m,id = 0;
struct node {
	int x,y,val;
} a[N];
int f[N],res = 0;

inline int read() {
	int x = 0,f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

bool cmp(node a,node b) {
	return a.val < b.val;
}


int find(int x) {
	if (f[x] == x) return x;
	return find(f[x]);
}

void kruscal() {
	for (int i = 1; i <= n; ++ i ) f[i] = i;
	sort(a + 1,a + m + 1,cmp);
	int wc = 0;
	for (int i = 1; i <= m; ++ i ) {
		int x = a[i].x,y = a[i].y,val = a[i].val;
		if (find(x) == find(y)) continue;
		f[find(x)] = find(y);
		res += val;
		++ wc;
		if (wc == n - 1) break;
	}
	if (wc == n - 1) cout << res << endl;
	else cout << "orz" << endl;
}

signed main() {
	n = read(); m = read();
	for (int i = 1; i <= m; ++ i ) a[i].x = read(),a[i].y = read(),a[i].val = read();
	kruscal();
	return 0;
}

推荐习题

下面给出一些习题，建议读者自己去尝试做一做。

P1546 [USACO3.1]最短网络 Agri-Net

P2872 [USACO07DEC]Building Roads S

P2330 [SCOI2005]繁忙的都市

P1194 买礼物

P1265 公路修建

\(\text{作者:songszh}\)