最小生成树（Prim）学习笔记
Before
为了做个挖水井去学了 Prim 虽然根本不是算法的锅
前置知识是 \(dijkstra\), 有一定相似度
Prim
\(Kruskal\) 是一种适用于稀疏图的算法，而对于稠密图，也有其适用的算法——Prim。
核心思想
Prim 主要处理的是点，和 \(Kruskal\) 的针对边来处理不同。
为了方便表述，使用了“起点”和“终点”来形容，实际上所有边都是无向的。
与 \(dijkstra\) 类似，从任意一个点出发，选取这个点连接的所有边中，权值最小且终点未标记过的一条，标记这条边通向的点。再以新的点为起点，重复以上操作直到所有点都被标记。
这里除了选择的点是“距离上一个被标记的点距离最小”之外，与 \(dijkstra\) 的思想几乎相同。
时间复杂度 \(O(n^2)\), 但是在密集图中性能比 \(Kruskal\) 好。
堆优化
类似 \(dijkstra\) 的堆优化，Prim 也是有堆优化的。
在稀疏图中的时间复杂度是 \(O(m\log n)\), 但是在密集图中会被卡回 \(O(n^2)\), 甚至还不如不优化。
例题
挖水井
题面：P1550
一开始用 \(Kruskal\) 死活只有 \(10pts\), 后来换了 Prim 也只能拿 \(50pts\), 后来发现是思路错了，于是去看了个题解：
因为可以挖不止一口井，所以可以把挖井的花费看作是从水源往回运水的花费。新增点 \(n + 1\) 作为水源，把从点 \(i\) 挖井的花费看作 \(i\) 和 \(n + 1\) 之间边的边权，然后跑一个最短路的板子，大功告成。
代码是我用之前写的 dij 板子改的，足以看出 Prim 跟 dij 真的没什么大区别。
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 1e5 + 5;
int n, m, s, ans;
int head[N], to[2 * N], weal[2 * N], dis[N], nxt[2 * N], tot;
bool vis[N];
void add(int u, int v, int w) {
to[++tot] = v;
weal[tot] = w;
nxt[tot] = head[u];
head[u] = tot;
}
struct node {
int dis, pos;
};
bool operator < (const node &x, const node &y) {
return x.dis > y.dis;
}
priority_queue<node> q;
inline void prim() {
int cnt = 0;
dis[s] = 0;
q.push((node){0, s});
while(!q.empty()) {
node tem = q.top();
q.pop();
int x = tem.pos, d = tem.dis;
if(vis[x]) continue;
vis[x] = 1, ++cnt;
ans += d;
for(int i = head[x]; i; i = nxt[i]) {
int y = to[i], w = weal[i];
if(dis[y] > w) {
dis[y] = w;
if(!vis[y]) q.push((node){dis[y], y});
}
}
}
if(cnt < n) ans = 0x7fffffff;
}
int main() {
scanf("%d", &n);
++n;
int w;
for(int i = 1; i < n; ++i) {
scanf("%d", &w);
add(n, i, w);
add(i, n, w);
}
for(int i = 1; i < n; ++i) for(int j = 1; j < n; ++j) {scanf("%d", &w); add(i, j, w);}
for(int i = 1; i <= n; ++i) dis[i] = 0x7fffffff;
s = 1;
prim();
printf("%d", ans);
return 0;
}