使用 Kruskal 算法按边权从小到大选不成环的边，并用并查集维护连通块。
OJ: luogu
题目 ID: P3366
难度:普及
标签:模板最小生成树Kruskal并查集图论
创建: 2026-01-03 09:38
更新: 2026-10-07 12:15
前置题目
后置题目
roj 1386打击犯罪(black)B 在倒序加点时把 A 教的「用并查集判断两端是否属于不同连通块、不同才合并」直接用作加边判据（main.py 中调用 dsu.unite(i, j)，由并查集内部在两端根不同时才合并并按大小累加 sz），并沿用 A 的 union-by-size 与 sz 累加，只在其上叠加 A 未教的「前缀删点=只看后缀」倒序等价与 f(k) 单调不增的首触发即答案判定。roj 3106银河英雄传说B 把 A 教的「用 find 求根、比较根是否相同来判定两元素是否同一连通块」直接用作同列判定（main.py 的 rx, ry = find(x), find(y) 与 rx != ry 分支，M 合并仍沿用 A 的按根挂树与根上规模累加），只在其上叠加 A 未教的 front 偏移量与从根向叶累加的路径压缩，把并查集从平凡连通块升级为带权并查集。roj 1489「一本通 3.1 练习 2」构造完全图B 的观察二把 A 教的「边权升序 + 并查集合并两个不同连通块」当作骨架，合并时用块大小乘积批量累计每个点对的路径最大边权，再叠加 A 未教的「补边权取下界 M+1」这一新观察。luogu P1621集合B 沿用 A 的并查集判两端不同集合才合并并计数的步骤，用筛法枚举质因数把区间倍数两两 union 出最终集合数roj 1393联络员B 的可选边阶段完全复用了 A 教的按权排序加并查集判环的 Kruskal 选边步骤，只是先用并查集把必选边缩成连通块再对可选边跑同一流程luogu P1525[NOIP 2010 提高组] 关押罪犯B 复用 A 教的「按权排序逐边处理、用并查集 find 判两端是否已连通」这一步做贪心取舍（第一次 find 同组处即答案），再叠加 A 未教的 2n 扩展域并查集表达异组约束与最大值最小化目标。luogu P2504[HAOI2006] 聪明的猴子B 复用 A 的最小生成树构造步骤（B 用 Prim 实现）并取树上最大边作为连通全图的最小跳距luogu P2916[USACO08NOV] Cheering up the Cow GB 把边权改写成 2L+C_u+C_v 后直接复用 A 教的 Kruskal 选边步骤（排序、并查集判两端异块才合并累加），再叠加树上每边走两次与点权分摊到边的代价改写luogu P8710[蓝桥杯 2020 省 AB1] 网络分析B 复用 A 的并查集判连通与合并步骤，把每次真实合并事件记成合并树虚点再 DFS 下传消息标记luogu P6121[USACO16OPEN] Closing the Farm GB 的动态连通性维护复用 A 的「并查集维护连通块、不同集合就合并」这一步（components 计数随合并增减，==1 判全连通），再叠加 A 未教的倒序重开（逆过程）建模与答案倒回原顺序。luogu P4047[JSOI2010] 部落划分B 复用 A 的 Kruskal 并查集加边循环，把终止条件从连通改成集合数等于 k，遇到的第一条跨集合边即答案
题意
给定一个无向带权图，求最小生成树权值和。
如果图不连通，输出 orz。
思路
先看一个可以直接验证想法的朴素解：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
const int MAXM = 25;
struct Edge {
int u;
int v;
int w;
};
int n, m;
Edge edges[MAXM];
int fa[MAXN];
int find_set(int x) {
if (fa[x] == x) {
return x;
}
fa[x] = find_set(fa[x]);
return fa[x];
}
bool check_mask(int mask, long long &sum) {
int cnt = 0;
sum = 0;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 0; i < m; i++) {
if ((mask & (1 << i)) == 0) {
continue;
}
cnt++;
sum += edges[i + 1].w;
int fu = find_set(edges[i + 1].u);
int fv = find_set(edges[i + 1].v);
if (fu == fv) {
return false;
}
fa[fu] = fv;
}
if (cnt != n - 1) {
return false;
}
int root = find_set(1);
for (int i = 2; i <= n; i++) {
if (find_set(i) != root) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
long long ans = -1;
for (int mask = 0; mask < (1 << m); mask++) {
long long sum;
if (check_mask(mask, sum)) {
if (ans == -1 || sum < ans) {
ans = sum;
}
}
}
if (ans == -1) {
cout << "orz\n";
} else {
cout << ans << '\n';
}
return 0;
}正式做法使用 Kruskal。
把所有边按权值从小到大排序。依次考虑每条边：如果这条边连接的是两个不同连通块，就把它加入生成树；否则加入它会成环，跳过。
连通块用并查集维护。
最后如果选出的边数是 n-1，说明得到了最小生成树；否则图不连通。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MAXM = 200005;
struct Edge {
int u;
int v;
int w;
};
int n, m;
Edge edges[MAXM];
int fa[MAXN], sz[MAXN];
bool cmp_edge(const Edge &a, const Edge &b) {
return a.w < b.w;
}
void init_dsu() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
sz[i] = 1;
}
}
int find_set(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
bool unite_set(int x, int y) {
int fx = find_set(x);
int fy = find_set(y);
if (fx == fy) {
return false;
}
if (sz[fx] < sz[fy]) {
swap(fx, fy);
}
fa[fy] = fx;
sz[fx] += sz[fy];
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
sort(edges + 1, edges + m + 1, cmp_edge);
init_dsu();
long long ans = 0;
int cnt = 0;
for (int i = 1; i <= m; i++) {
if (unite_set(edges[i].u, edges[i].v)) {
ans += edges[i].w;
cnt++;
if (cnt == n - 1) {
break;
}
}
}
if (cnt != n - 1) {
cout << "orz\n";
} else {
cout << ans << '\n';
}
return 0;
}复杂度
排序复杂度为：
text
O(m log m)并查集操作近似线性，空间复杂度为
总结
Kruskal 的核心是：每次选择当前最小的、连接两个不同连通块的边。
并查集负责快速判断一条边是否会成环。
