对于一个无向连通图，其最小生成树为边权和最小的生成树。即选取连边，使得节点间互相连通，且边权之和最小。
先将输入的边权从小到大排序，并记录边所连接的节点，从最小边权的边开始连接节点，若遇到连接之后会成环的情况则这条边不连接。连接 $n-1$ 条边后，即可得到最小生成树。
这个过程中，利用并查集维护连接起来的节点。
#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 5;
const int N = 5e3 + 8;
struct edge {
int u, v, w; // 储存边连接的两个节点以及边权
} e[M];
bool cmp(edge a, edge b) { return a.w < b.w; }
int n;
int fa[N];
void init() {
for (int i = 1; i <= n; ++i)
fa[i] = i;
}
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
bool unite(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
fa[fx] = fy;
return true;
}
return false; // 若两个节点还没连接，返回 true，否则返回 false
}
int main() {
int m;
cin >> n >> m;
init();
for (int i = 1; i <= m; ++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e + 1, e + m + 1, cmp); // 从小到大排列边权
int edgeCnt = 0, minSum = 0; // 记录连边数量、最小边权和
for (int i = 1; i <= m; ++i) {
if (unite(e[i].u, e[i].v)) {
edgeCnt++;
minSum += e[i].w;
}
}
if (edgeCnt == n - 1) // 判断是否连通
cout << minSum;
else
cout << "orz";
return 0;
}
设置一个集合用于存放点，一个小根堆用于存放边，然后：
从任意一个点开始，将其加入到集合，并将所有连边（注意在 Prim 算法中，无向图的边要拆分为两条有向边）加入堆。
然后，弹出堆顶元素（即权值最小的边），查看边去往的点 x，若 x 已经在集合中出现过，不做任何事；若没有出现，则将 x 加入集合，并且将 x 的所有连边加入堆。
当堆中没有元素时，最小生成树也就得到了。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 8;
struct edge {
int to, w; // 记录去向的节点、边权
};
bool operator<(edge a, edge b) { return a.w > b.w; }
// 重载运算符制造小根堆，没有重载不能编译
vector<edge> G[N];
int n;
priority_queue<edge> pq;
bool st[N]; // st[i] = true 表明出现了
int main() {
int m;
cin >> n >> m;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w}); // 建反向边
}
for (auto e : G[1]) {
pq.push(e); // 挑选节点 1 为起始点，将连边加入堆
}
int nodeCnt = 1, minSum = 0; // 记录得到的节点数、最小边权和
st[1] = true; // 1 已出现
while (pq.size()) {
edge eg = pq.top();
pq.pop();
int nextNode = eg.to;
int length = eg.w;
if (!st[nextNode]) {
// nextNode 未出现，则将这条边加入最小生成树
nodeCnt++;
st[nextNode] = true;
minSum += length;
for (auto e : G[nextNode])
pq.push(e); // 将 nextNode 的连边加入堆
}
}
if (nodeCnt == n) // 判断是否选到了所有节点
cout << minSum;
else
cout << "orz";
return 0;
}