1 从一棵树扩展
最小生成树 中,Kruskal 同时维护多个连通块,按边权排序后逐步合并。
Prim 从任意一个点出发,维护已经入树的点集
两个算法都选择最轻跨切边。区别在于:Kruskal 合并一片森林,Prim 只扩展一棵树。
2 入树代价
对每个尚未入树的点
它表示从当前树中接入
pre[v] 记录提供该边的树内顶点。每次选出 dis 最小的未入树顶点
if (!vis[v] && w < dis[v]) {
dis[v] = w;
pre[v] = u;
}
第一次还没有树,约定起点 dis[1]=0,其余点为无穷大。这个
3 示例
沿用基础篇的五点八边图。每次更新后,未入树点的代价如下:
| 已入树点集 |
dis[2] |
dis[3] |
dis[4] |
dis[5] |
累计权值 |
|---|---|---|---|---|---|
| — | |||||
| — | — | ||||
| — | — | — | |||
| 全部顶点 | — | — | — | — |
按代码“严格变小才更新”的约定,
3.1 演示
可在下面的外部演示中观察跨切边与入树点的变化:
最小生成树:Primanima14 正确性
设已经选出的树边为
若
起点不含任何边,不变量成立;每次扩展都保持不变量。选完全部点后,已经是一棵生成树,故它就是 MST。
若所有未入树点的 dis 都为无穷大,表示不存在跨过
5 与 Dijkstra 的区别
两种算法都可以“取最小代价顶点,再更新邻点”,但 dis 的含义不同:
| 算法 | dis[v] 含义 |
经由 |
|---|---|---|
| Prim | 从当前树接入 |
|
| Dijkstra | 从固定源点到 |
例如三角形边权为
加入
所以 Prim 的更新中不能加 dis[u]。Prim 可以处理负权边,其证明不依赖 Dijkstra 的非负权条件。
6 邻接矩阵
每轮扫描全部未入树点,选代价最小者,再扫描它与所有点之间的边。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2000 + 5; // 邻接矩阵版本只用于 n <= 2000
const ll INF = 1LL << 62;
ll g[maxn][maxn], dis[maxn];
int pre[maxn];
bool vis[maxn];
bool prim(int n, ll &answer) {
for (int i = 1; i <= n; ++i) {
dis[i] = INF;
pre[i] = 0;
vis[i] = false;
}
dis[1] = 0; // 第一个点没有入树边,这个 0 不代表原图中的边
answer = 0;
for (int step = 1; step <= n; ++step) {
int u = 0;
for (int v = 1; v <= n; ++v) {
if (!vis[v] && (u == 0 || dis[v] < dis[u])) u = v;
}
if (u == 0 || dis[u] == INF) return false;
vis[u] = true;
answer += dis[u];
for (int v = 1; v <= n; ++v) {
if (!vis[v] && g[u][v] < dis[v]) {
dis[v] = g[u][v]; // 最便宜的入树边;这里不加 dis[u]
pre[v] = u;
}
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) g[i][j] = INF;
}
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
if (u == v) continue;
g[u][v] = g[v][u] = min(g[u][v], w); // 重边只保留最小值
}
ll answer;
if (prim(n, answer)) cout << answer << '\n';
else cout << "orz\n";
return 0;
}
矩阵中的无边位置使用 INF,不能用
代码与基础篇使用同一输入格式:先输入 orz。使用基础篇的样例,答案为
本矩阵模板容量为
初始化与选点各需 pre[v] 还可以用于记录最终树边。
7 堆优化
稀疏图不必每轮扫描全部点,可以把 (dis[v],v) 放入小根堆。某点代价变小时,直接插入新的候选;旧候选留在堆中,取出时跳过已经入树的点。
一个点的最新候选不大于它自己的旧候选,会先被取出。第一次取出时便以当前最小入树代价入树,之后都被 vis 排除;每个点的代价只累加一次。
堆优化完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
const ll INF = 1LL << 62;
struct Edge {
int to;
ll w;
};
vector<Edge> g[maxn];
ll dis[maxn];
int pre[maxn];
bool vis[maxn];
bool prim(int n, ll &answer) {
for (int i = 1; i <= n; ++i) {
dis[i] = INF;
pre[i] = 0;
vis[i] = false;
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> heap;
dis[1] = 0;
heap.push({0, 1});
answer = 0;
int selected = 0;
while (!heap.empty()) {
auto [cost, u] = heap.top();
heap.pop();
if (vis[u]) continue; // 旧候选可能仍在堆内,每个点只能入树一次
vis[u] = true;
++selected;
answer += cost;
for (auto [v, w] : g[u]) {
if (!vis[v] && w < dis[v]) {
dis[v] = w;
pre[v] = u;
heap.push({dis[v], v});
}
}
}
return selected == n;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
ll answer;
if (prim(n, answer)) cout << answer << '\n';
else cout << "orz\n";
return 0;
}
这里使用普通 priority_queue,没有直接修改堆内旧项,因此堆中可能同时保存同一点的多个候选。每条边只被扫描常数次,最多产生
空间为
本模板支持
8 隐式完全图
有些图没有直接输入全部边,而是给出点坐标,任意两点都能连边。显式存储全部
此时仍可使用朴素 Prim:选出
几何距离题还需把边权、dis 和累加和统一改为浮点类型,不能直接复制整数版的读入与存储。
9 边界
- 起点任选;连通图上,从不同起点得到的 MST 边集可能不同,但总权值相同。
- 零权、负权均可正常比较,边权与总和使用
ll;本系列按使用。 时起点独自入树,答案为 ,不需要真实边。 - 朴素版选不到有限代价顶点、堆版不能访问所有点,都是不连通的表现。
- 遍历部分顶点得到的权值,不是整个原图的 MST 答案。
- 多组数据时,要重置
dis、vis、pre及图的存储;两个算法函数已重置自己的选点状态。
10 练习
10.1 手算
- 为什么起点不需要累加真实边权?
- 三角形边权为
时,Prim 的总权值与从 出发的最短路径树的总边权各是多少? - 堆内某顶点出现两次,能否把两次弹出的代价都加入答案?
参考结果
- 起点构成单点树,没有入树边;其余
个点各用一条边接入。 - MST 为
;最短路径树使用边 、 ,总边权为 。 - 不能。一个点只能入树一次,旧候选需要跳过。
10.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 矩阵输入 | luogu P1546: [USACO3.1] 最短网络 Agri-Net | 从邻接矩阵直接选点、更新入树代价。 |
| 虚拟源点 | luogu P1550: [USACO08OCT] Watering Hole G | 将挖井看作连向虚拟水源的边,用 Prim 统一处理两种费用。 |
| 完全图 | luogu P2872: [USACO07DEC] Building Roads S | 点间边权为欧氏距离,已有道路按零费用处理,求新增道路总长度。 |
| 堆版对照 | luogu P3366: 【模板】最小生成树 | 与 Kruskal 使用相同数据,对比答案与不连通判断。 |
下一篇 瓶颈路 讨论:最小生成树如何同时回答两点之间的瓶颈值。
11 相关题解
暂无相关题解