核心逻辑与数学原理
最小生成树（Minimum Spanning Tree, MST）问题的本质是：在一个包含 $N$ 个点、$M$ 条边的带权无向连通图 $G=(V, E)$ 中，选择一个边集 $T \subseteq E$，使得 $(V, T)$ 构成一棵拓扑连通树，且该树的所有边权之和 $\sum_{e \in T} w(e)$ 达到全局最小值。
在 NOIP 体系下，Kruskal 与 Prim 算法分别基于截然不同的图论代数原理构建：
1. 边集贪心范式：Kruskal 算法
Kruskal 算法的核心数学基石是管辖割边定理（Cut Property）与贪心扩张。
- 数学原理：将图中所有边按照边权进行非降序（从小到大）精确排序。从空边集开始，依次审视每条边。若当前被审视边的两个端点在当前的生成森林中处于不同的连通分量，则该边必然是连接这两个连通分量的“最短割边”。将其强制并入边集，直至合拢出 $N-1$ 条边。
- 并查集维护：算法将“连通分量的识别与合并”完美同构于并查集（DSU）的
find与merge操作。 - 复杂度定理：算法的时间复杂度瓶颈在于边权排序，严格为 $O(M \log M)$。由于其本质是面向边集的迭代，极度适合稀疏图。
2. 点集拓扑扩张范式：Prim 算法
Prim 算法的核心物理本质是蓝白点集合的切分扩张，其结构上与 Dijkstra 算法高度同构。
- 数学原理：将图中的定点划分为两个集合：已加入生成树的熟化点集 $S$（蓝点），和未加入的悬空点集 $T$（白点）。每次从 $T$ 集合中强制挑选一个距离当前整棵生成树（而非距离源点）最近的节点 $u$，将其划归入 $S$，同时用 $u$ 的所有出边去刷新其余白点到整个 $S$ 集合的拓扑最短距离。
- 复杂度定理：配合优先队列（小根堆）维护白点到树的最小距离，单次松弛复杂度为 $O(\log V)$，总时间复杂度严格控制在 $O((V+E)\log V)$。由于其复杂度与边数 $M$ 的对数无关，在稠密图（$M \approx V^2$）中展现出统治级的性能。
算法推导与状态设计
1. Kruskal 状态设计
定义并查集数组 fa[i]。
- 边结构体封装：
struct Edge {
int u, v;
long long w;
bool operator<(const Edge& rhs) const { return w < rhs.w; }
};- 状态转移（并查集判环）： 对于排好序的边 $e_i$，令 $root_u = \text{find}(e_i.u), \, root_v = \text{find}(e_i.v)$。
$$\text{if } (root_u \neq root_v) \quad \text{fa}[root_u] = root_v, \,\, \text{edge\_cnt} \leftarrow \text{edge\_cnt} + 1$$
2. Prim 堆优化状态设计
定义 $dist[i]$ 为白点 $i$ 到当前已生成的 MST 边集树面的拓扑最短距离。
优先队列中存储的状态为二元组 $(d, u)$，其中 $u$ 为节点编号，$d$ 为当前的 $dist[u]$。
小根堆顶元素驱动状态转移方程：
$$dist[v] = \min(dist[v], w(u, v)) \quad (\forall v \in T, \, (u, v) \in E)$$
物理含义：当蓝点集扩展了 $u$ 后，悬空点 $v$ 到树面的最短距离，可能被新加入的边界边 $w(u, v)$ 刷新。
C++ 标准源码（Kruskal 工业级模板）
#include <iostream>
#include <vector>
#include <algorithm>
const int MAXN = 100005;
const int MAXM = 300005;
struct Edge {
int u, v;
long long w;
// 严格按边权非降序排列
bool operator<(const Edge& rhs) const {
return w < rhs.w;
}
};
Edge edges[MAXM];
int fa[MAXN];
// 并查集核心：路径压缩
int find_set(int i) {
if (fa[i] == i) return i;
return fa[i] = find_set(fa[i]); // 关键踩坑点：必须进行路径压缩，否则链状树会导致复杂度退化
}
// 并查集内连通块合并
bool union_set(int i, int j) {
int root_i = find_set(i);
int root_j = find_set(j);
if (root_i != root_j) {
fa[root_i] = root_j;
return true; // 成功合并，说明原本不连通，此边合法
}
return false; // 原本已连通，若加边必成环，拒绝
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
if (!(std::cin >> n >> m)) return 0;
for (int i = 0; i < m; ++i) {
std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
// 核心驱动：对全量边集进行快速排序
std::sort(edges, edges + m);
// 初始化并查集底座
for (int i = 1; i <= n; ++i) fa[i] = i;
long long mst_weight = 0;
int edges_selected = 0;
for (int i = 0; i < m; ++i) {
if (union_set(edges[i].u, edges[i].v)) {
mst_weight += edges[i].w;
edges_selected++;
if (edges_selected == n - 1) break; // 提前熟化拦截：已凑齐 N-1 条边
}
}
// 拓扑连通性校验
if (edges_selected < n - 1) {
std::cout << "orz\n"; // 图本身不连通，无法构造生成树
} else {
std::cout << mst_weight << "\n";
}
return 0;
}
NOIP 实战避坑指南
- 完全不看数据特征，稠密网格图盲目选用 Kruskal： 若题目给出的图是严格的稠密图，例如完全图或大基数网格图，满足 $V=5000, M \approx 1.2 \times 10^7$。若选用 Kruskal 算法，其排序开销 $M \log M$ 将让内存膨胀且 CPU 时间直接暴崩触发 TLE。此时，必须敏锐切入 $O(V^2)$ 的朴素 Prim 或 堆优化 Prim 算法，因为 Prim 的松弛状态完全不依赖于边数的全局排序。
- 并查集初始化漏写或深度递归未路径压缩：
在 Kruskal 的
main函数中，极其容易遗漏for (int i = 1; i <= n; ++i) fa[i] = i;这句标定。若不初始化，所有的fa残留为 0，find_set将瞬间陷入死循环或内存越界。此外，若在find_set中漏掉滚动赋值fa[i] = find_set(fa[i])（路径压缩），并查集退化为长链，单次合并退化为 $O(V)$，导致 Kruskal 算法退化为 $O(MV)$ 的暴力，彻底丢失时效性。
经典 NOIP/洛谷 真题
1. 洛谷 P3366 【模板】最小生成树
- 题意描述：
给定一个包含 $N$ 个点、$M$ 条无向边的带权图，求该图的最小生成树的边权之和。若图不连通，输出
orz。 - 问题本质与核心思路： 最标准、最纯净的最小生成树模板应用。数据范围属于常规稀疏图。核心思路是直接套用 Kruskal 算法：结构体封装存储三元组，按权值升序排序，利用路径压缩并查集遍历每条边。用计数器累计合并成功的次数，若最终等于 $N-1$ 则输出累计的边权和，否则输出不连通标志。
2. 洛谷 P1194 买礼物
- 题意描述： 要买 $B$ 件物品，单独买每件物品的价格都是 $A$。但是物品之间存在优惠关系：如果已经买了物品 $X$，再买物品 $Y$ 就可以享受优惠价 $W_{X,Y}$。求买完所有物品所需的最小花费。
- 问题本质与核心思路： 稠密图建图并求 MST 的典型变形。由于“已经买了 $X$ 才能以优惠价买 $Y$”，这种依赖关系和价格的最小化选择，本质上就是在一张网络中求图的最小生成树。 硬核建图策略：引入一个虚拟节点 $0$ 号点作为“市场源点”。从 $0$ 号点向所有的物品 $1 \dots B$ 连一条权值为 $A$ 的有向边（代表原价购买作为第一件物品）。如果物品 $X$ 和 $Y$ 之间有优惠价 $W_{X,Y}$ 且 $W_{X,Y} < A$，则在 $X$ 和 $Y$ 之间连一条权值为 $W_{X,Y}$ 的无向边。 在这张包含了 $B+1$ 个节点的全新图网上跑一次标准的 MST 算法。由于物品间的优惠关系通常以稠密矩阵形式给出，此题选用 Prim 或 Kruskal 均能游刃有余地解决。总花费即为 MST 的总权值。