最小生成树（竞赛）

一、介绍

最小生成树一般针对的是无向图，用 n - 1 条边连接 n 个节点，并且权值最小。

接下来介绍两种算法：克鲁斯卡尔算法，普利姆算法

例题：最小生成树

P3366 【模板】最小生成树 - 洛谷

二、克鲁斯卡尔算法

1、实现思路

不断加边的贪心算法。

按权值从小到大加入不会使当前最小生成树有环的边，一直加 n - 1 条。

步骤一：对所有边进行排序（一般是权值从大到小）

步骤二：循环加 n - 1 条不会成环的边（判环：看要加入边的起点和终点在不在同一个集合）

步骤三：循环结束后如果没有加到 n - 1 条边就说明无法生成

2、代码

// https://www.luogu.com.cn/problem/P3366
#include "bits/stdc++.h"
using namespace std;
int n, m;// 克鲁斯卡尔算法：每次选最短的边加入，如果构成环再换一条边，直到选完
// 每次加入边之前先看看起点终点是否在并查集，如果在那就是环要舍去
struct edge
{int s, e, v;edge(int _s, int _e, int _v):s(_s),e(_e),v(_v){}
};
vector<edge> e;int a[5010];
int find(int x)
{if(x == a[x]) return x;return a[x] = find(a[x]);
}void U(int x, int y)
{int p1 = find(x);int p2 = find(y);a[p1] = p2;
}bool issame(int x, int y)
{return find(x) == find(y);
}struct cmp
{bool operator()(edge e1, edge e2){return e1.v < e2.v;}
};void K()
{sort(e.begin(), e.end(), cmp());int cnt = 0;int ans = 0;for(int i = 0; i < m; i++){if(issame(e[i].s, e[i].e) == false){cnt++;ans += e[i].v;U(e[i].s, e[i].e);}}if(cnt == n - 1)cout << ans;else cout << "orz";
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);// 初始化并查集for(int i = 1; i <= n; i++)a[i] = i; for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;e.push_back({a, b, c});}K();return 0;
}

三、普利姆算法

1、实现思路

不断加点的贪心算法。

每次加入不在最小生成树中，且离树最近的点。

步骤一：初始化起点离树最近，dist[start] = 0;

步骤二：循环 n 次，查找 dist 最小且不在树中的节点，没找到就是无法生成最小生成树，找到了就加入节点，并且把新节点作为起点，更新未被加入节点的 dist 最小值

2、代码

// https://www.luogu.com.cn/problem/P3366
#include "bits/stdc++.h"
using namespace std;
int n, m;
int g[5010][5010];// 1.任意选择一个点作为起点
// 2.之后要在最小生成树中添加n个点
// 3.添加方式是先把起点所关联的点的权值更新在dist，在dist中找没被加入的权值最小的点，作为下一轮的起点。
void Prim()
{vector<int> dist(n + 1, 0x3f3f3f3f);vector<bool> st(n + 1, false);int ans = 0;// 假设起点为1dist[1] = 0;for(int i = 0; i < n; i++){int start = 0;for(int j = 1; j <= n; j++){if(st[j] == false && dist[start] > dist[j])start = j;}if(dist[start] == 0x3f3f3f3f){cout << "orz";return;}ans += dist[start];st[start] = true;for(int j = 1; j <= n; j++){dist[j] = min(dist[j], g[start][j]);}}cout << ans;
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);// 初始化并查集for(int i = 1; i <= n; i++)a[i] = i; for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;// 考虑重边 Prim()g[a][b] = g[b][a] = min(g[a][b], c);}Prim();return 0;
}

四、例题

1、买礼物

P1194 买礼物 - 洛谷

// https://www.luogu.com.cn/problem/P1194
#include "bits/stdc++.h"
using namespace std;
int a, b;
int fa[510];struct edge
{int s;int e;int w;
};
vector<edge> edges;bool cmp(edge edge1, edge edge2)
{return edge1.w < edge2.w;
}int find(int x)
{if(x == fa[x]) return x;return fa[x] = find(fa[x]);
}void U(int x, int y)
{int xx = find(x);int yy = find(y);if(xx == yy)return;fa[xx] = yy;
}bool issame(int x, int y)
{return find(x) == find(y);
}int ans = 0;
void K()
{sort(edges.begin(), edges.end(), cmp);for(int i = 0; i < edges.size(); i++){if(issame(edges[i].s, edges[i].e) == false){ans += edges[i].w;U(edges[i].s, edges[i].e);}}
}int main()
{cin >> a >> b;for(int i = 1; i <= b; i++)fa[i] = i;for(int i = 1; i <= b; i++){for(int j = 1; j <= b; j++){int x;cin >> x;if(i == j)continue;if(x != 0)edges.push_back({i, j, min(a, x)});else edges.push_back({i, j, a});}}K();cout << ans + a;return 0;
}

2、繁忙的都市

P2330 [SCOI2005] 繁忙的都市 - 洛谷

// https://www.luogu.com.cn/problem/P2330
#include <bits/stdc++.h>
using namespace std;
int n, m;
int fa[310];int find(int x)
{if(x == fa[x]) return x;return fa[x] = find(fa[x]);
}void merge(int x, int y)
{int xx = find(x);int yy = find(y);fa[xx] = yy;
}bool issame(int x, int y)
{return find(x) == find(y);
}struct edge
{int s, e, w;
};
vector<edge> edges;bool cmp(edge e1, edge e2)
{return e1.w < e2.w;
}int ans = 0;
void K()
{sort(edges.begin(), edges.end(), cmp);for(int i = 0; i < m; i++){if(issame(edges[i].s, edges[i].e) == false){ans = max(ans, edges[i].w);merge(edges[i].s, edges[i].e);}}
}
int main()
{cin >> n >> m;for(int i = 0; i < m; i++){int s, e, w;cin >> s >> e >> w;edges.push_back({s, e, w});}for(int i = 1; i <= n; i++)fa[i] = i;K();cout << n - 1 << ' ' << ans;return 0;
}

3、滑雪

P2573 [SCOI2012] 滑雪 - 洛谷

// https://www.luogu.com.cn/problem/P2573
// 对起点进行一次dfs就能统计出合法路径和最多能走到的点
// 克鲁斯卡尔算法是可以解决有向图的问题的，但是需要注意的是环路的判断不再是简单的把两个点放到一个集合中，因为有了方向，所以要把 x->y 路径进行合并的话应该是 fa[yy] = xx;
// 这道题边最重要的是终点尽量高，其次才是路径权值小#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;
int n, m;
const int N = 1e5 + 10;
int h[N];
int fa[N];
vector<pii> E[N];int find(int x)
{if(x == fa[x]) return x;return fa[x] = find(fa[x]);
}struct edge
{int s, e, w;
};
vector<edge> edges;bool cmp(edge e1, edge e2)
{return (h[e1.e] > h[e2.e]) || (h[e1.e] == h[e2.e] && e1.w < e2.w);
}int cnt = 0;
bool vis[N];
void dfs(int s)
{vis[s] = true;cnt++;for(auto& p : E[s]){int x = p.first;int y = p.second;edges.push_back({s, x, y});if(vis[x] == false)dfs(x);}
}ll ans = 0;
void K()
{sort(edges.begin(), edges.end(), cmp);for(int i = 0; i < edges.size(); i++){int ss = find(edges[i].s);int ee = find(edges[i].e);if(ss != ee){ans += edges[i].w;fa[ee] = ss;}}
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++)fa[i] = i;for(int i = 1; i <= n; i++)cin >> h[i];for(int i = 0; i < m; i++){int s, e, w;cin >> s >> e >> w;if(h[s] >= h[e])E[s].push_back({e, w});if(h[s] <= h[e])E[e].push_back({s, w});}dfs(1);K();cout << cnt << ' ' << ans;return 0;
}

通过这道题我们知道前面的算法可以解决有向图的问题，只不过判环的逻辑需要严谨，谁是谁的父节点在并查集中一定不能弄反，不然关系混乱的情况下有向边会被表示错，导致答案出错。