最小生成树
概念
- 生成树:n 个点、n-1 条边,连通且无环。
- 最小生成树 MST:边权总和最小的生成树。
- 最小瓶颈树: 所有生成树中最大边权最小的树。最小瓶颈树一定是 MST。
Kruskal(边排序 + 并查集)
复杂度
- 排序:$O(m log m)$
- 并查集:$O(m α(n)) + O(n)$
- 总:$O(m log m) + O(n)$。 稀疏图首选。
思路:
- 先将所有边按权值排序。
- 重复以下操作:
- 选择一条最小权值的边 $(u, v, w)$。
- 如果 $(u, v)$ 不在并查集中,则将 $(v, u, w)$ 加入并查集。
- 否则,跳过该边。
- 最后得到的生成树即为最小生成树。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Edge {
int u, v, w;
bool operator<(const Edge& o) const { return w < o.w; }
};
struct DSU {
vector<int> f;
DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
f[y] = x; return true;
}
};
ll kruskal(int n, vector<Edge>& e) {
sort(e.begin(), e.end());
DSU dsu(n);
ll sum = 0, cnt = 0;
for (auto [u, v, w] : e) {
if (dsu.unite(u, v)) {
sum += w;
if (++cnt == n - 1) break;
}
}
return cnt == n - 1 ? sum : -1; // -1 表示不连通
}
题目 1 最小生成树(Kruskal)
给定一个无向连通图,边有权值,求其最小生成树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 1e6 + 10;
vector<int> fa(N);
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) {
return false;
}
fa[fx] = fy;
return true;
}
int n, m;
struct Edge {
int u, v, w;
bool operator<(Edge &o) { return w < o.w; }
};
void solve() {
cin >> n >> m;
vector<Edge> edges;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
sort(edges.begin(), edges.end());
init(n);
int cnt = 0;
int sum = 0;
for (auto [u, v, w] : edges) {
if (merge(u, v)) {
cnt++;
sum += w;
}
}
cout << ((cnt == n - 1) ? to_string(sum) : "orz") << endl;
}
Prim(点扩展 + 优先队列)
复杂度
- 二叉堆:O(m log n)
- Fibonacci 堆(理论):O(m + n log n)
- 一般用
priority_queue
,O(m log n)。稠密图可转邻接矩阵暴力 O(n²) 版本。
思路
- 选择一个源点,将其加入优先队列。
- 重复以下操作:
- 从优先队列中取出最小权值的边 $(u, v, w)$。
- 如果 $(u, v)$ 未被访问过,则将 $(v, u, w)$ 加入优先队列。
- 将 $(u, v)$ 标记为已访问。
- 最后得到的生成树即为最小生成树。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using PII = pair<int,int>;
ll prim(int n, const vector<vector<PII>>& g) {
vector<char> vis(n);
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.emplace(0, 0); // {dist, node}
ll sum = 0, cnt = 0;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u] = 1; sum += d; ++cnt;
for (auto [v, w] : g[u])
if (!vis[v]) pq.emplace(w, v);
}
return cnt == n ? sum : -1;
}
题目 2 最小生成树(Prim)
给定一个无向连通图,边有权值,求其最小生成树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int n, m;
struct MaxHeapCmp {
bool operator()(const pair<int, int> &a, const pair<int, int> &b) const {
return a.second > b.second;
}
};
void solve() {
cin >> n >> m;
vector<vector<pair<int, int>>> g(n + 1);
priority_queue<pair<int, int>, vector<pair<int, int>>, MaxHeapCmp> heap;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for (auto edge : g[1]) {
heap.push(edge);
}
vector<bool> set(n + 1);
int nodeCnt = 1;
set[1] = true;
int ans = 0;
while (!heap.empty()) {
auto [v, w] = heap.top();
heap.pop();
if (!set[v]) {
nodeCnt++;
set[v] = true;
ans += w;
for (auto edge : g[v]) {
heap.push(edge);
}
}
}
cout << ((nodeCnt == n) ? to_string(ans) : "orz");
}
题目 3 水资源分配优化
1
2
3
4
5
6
7
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i,我们有两种可选的供水方案:一种是直接在房子内建造水井
成本为 wells[i - 1] (注意 -1 ,因为 索引从0开始 )
另一种是从另一口井铺设管道引水,数组 pipes 给出了在房子间铺设管道的成本,
其中每个 pipes[j] = [house1j, house2j, costj]
代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本
思路: 将井看做一个节点,将建井看做修村庄到井的路,管道看做修村庄间的路,则问题转化为求修出让所有村庄到井的路的最小代价。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
vector<int> fa;
void init(int n){
fa.resize(n + 1);
for(int i = 0; i <= n; i++){
fa[i] = i;
}
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx == fy) {
return false;
}
fa[fx] = fy;
return true;
}
struct Edges {
int u, v, w;
bool operator<(const Edges& o) const {
return w < o.w;
}
};
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) { // wells为修井的成本,pipes为管道的成本
init(n);
vector<Edges> edges;
for(int i = 0; i < n; i++){
edges.push_back({0, i + 1, wells[i]}); // 0 代表水源点 i + 1为村庄编号 wells[i]为代价
}
for(int i = 0; i < pipes.size(); i++){
edges.push_back({pipes[i][0], pipes[i][1], pipes[i][2]});
}
sort(edges.begin(), edges.end());
int ans = 0;
for(auto [u, v, w] : edges){
if(merge(u, v)){
ans += w;
}
}
return ans; // 题目保证所有节点一定联通
}
题目 4 检查边长度限制的路径是否存在
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
vector<int> fa;
void init(int n) {
fa.resize(n);
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) {
return false;
}
fa[fx] = fy;
return true;
}
bool isSameSet(int a, int b) { return find(a) == find(b); }
vector<vector<int>> questions;
vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>> &edges, vector<vector<int>> &queries){
int m = edges.size();
int k = queries.size();
// 步骤1:绑定查询原始索引
for (int i = 0; i < k; i++) {
questions.push_back(
{queries[i][0], queries[i][1], queries[i][2], i});
}
// 步骤2:双排序(边和查询都按限制值升序)
sort(questions.begin(), questions.end(),
[](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });
sort(edges.begin(), edges.end(),
[](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });
// 步骤3:初始化并查集
init(n);
vector<bool> ans(k);
// 步骤4:双指针处理
for (int i = 0, j = 0; i < k; i++) { // i遍历查询,j遍历边
// 合并所有边权小于当前查询限制的边
while (j < m && edges[j][2] < questions[i][2]) {
merge(edges[j][0], edges[j][1]);
j++;
}
// 检查当前查询的连通性
ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);
}
return ans;
}
题目 5 最小瓶颈树-繁忙的都市
最小瓶颈树
所有生成树中最大边权最小的树。
结论:MST 一定也是最小瓶颈树,反之不一定。因此直接跑 MST 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 400;
int n, m;
vector<vector<pair<int, int>>> g(N);
vector<int> fa;
void init(int n) {
fa.resize(n + 1);
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
bool merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy) {
return false;
}
fa[fx] = fy;
return true;
}
struct edges {
int u, v, w;
bool operator<(const edges &o) { return w < o.w; }
};
void solve() {
cin >> n >> m;
vector<edges> edges;
for (int i = 0; i < m; i++) {
int uu, vv, ww;
cin >> uu >> vv >> ww;
edges.push_back({uu, vv, ww});
}
sort(edges.begin(), edges.end());
init(n);
int maxedge = -1;
for (auto [u, v, w] : edges) {
if (merge(u, v)) {
maxedge = max(w, maxedge);
}
}
cout << n - 1 << " " << maxedge << endl;
}