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

• 题目
  

• 最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

• 思路

  kruskal算法

因为要判断集合容斥

所以用了并查集(My blog)~QwQ~

上代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e3 + 10,
          maxm = 2e5 + 10;
int par[maxn], size[maxn], n, m, t, ans;
//  array-par:并查集-father node
//  array-size:并查集-size of the tree(按秩合并)
//  data-n:点数; data-m:边数; data-t:判断最小生成树是否构造完成; data-ans:最小生成树权值和

struct Edge {
	int u, v, w; // 起始边, 终点边, 权值
	
	inline bool operator < (const Edge &e) const {
		return w < e.w;
	} // kruskal:按照权值升序排序
} a[maxm]; // Edge

inline int find(const int &x) {
	return par[x] == x ? x : par[x] = find(par[x]);
} // 并查集 find father + 路径压缩(将该节点接到父节点下)

inline void unite(int x, int y) {
	x = find(x), y = find(y);
	if (size[x] > size[y]) swap(x, y);
	size[y] += size[x], par[x] = y;
} // 并查集 合集 + 按秩合并(将小树合并到大树上)

int main() {
	scanf("%d %d", &n, &m), t = n;
	for (int i = 1; i <= n; i++)
		par[i] = i, size[i] = 1;
    // 并查集初始化
	for (int i = 1; i <= m; i++)
		scanf("%d %d %d", &a[i].u, &a[i].v, &a[i].w);
    // init
	sort(a + 1, a + m + 1); // 按照权值排序
	for (int i = 1; i <= m; i++) {
		if (find(a[i].u) == find(a[i].v))
			continue;
        // 在不属于同一集合的情况下合并(greedy)
		unite(a[i].u, a[i].v), ans += a[i].w, t--;
        // 加边
		if (t < 2) return printf("%d", ans), 0;
        // 最小生成树条件
	}
	return puts("orz"), 0;
    // hehe~若该图非连通图
}

Prim : (:<)