MST
最小生成树(MST:minimum-cost spanning tree)也称最小支撑树,任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通). 加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.最小代价生成树是其所有生成树中代价最小的生成树。
Prim在稠密图中比Kruskal优,在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值,Kruskal是直接将边排序。
https://www.luogu.com.cn/problem/P3366
Prim算法
这里的代码去掉了select数组,使用dist数组来确定是否在MST内。因为MST内的点的dist值总是置为0。
#include<bits/stdc++.h>
//#define LOCAL
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;
struct {
int to, w, next;
} edge[MAXN * 2];
int head[MAXN], dist[MAXN];
int cnt = 0;
int n;
int x, y, m, z;
void add(int u, int v, int w) {
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int prim() {
int now = x, minn, ans = 0, tot = 0;
fill(dist, dist + MAXN, inf);
for (int i = head[now]; i != -1; i = edge[i].next) {
dist[edge[i].to] = min(dist[edge[i].to], edge[i].w);
}
while (++tot < n) {
dist[now] = 0;
minn = inf;
now = -1;
for (int i = 1; i <= n; ++i) {
if (dist[i] && minn > dist[i]) {
minn = dist[i];
now = i;
}
}
if (now == -1) {
ans = -1;
return ans;
}
ans += minn;
for (int i = head[now]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (dist[v] > edge[i].w && dist[v]) {
dist[v] = edge[i].w;
}
}
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m;
memset(head, -1, sizeof(head));
while (m--) {
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
int res = prim();
if (res == -1) { print("orz"); } else print(res);
}
Kruskal算法,按边权值排序后加边,在判断是否成圈时用到了并查集。
#include<bits/stdc++.h>
//#define LOCAL
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;
int Rank[MAXN], fa[MAXN];
inline void init(int n) {
for (int i = 1; i < n; ++i) {
fa[i] = i;
Rank[i] = 1;
}
}
int find(int x) {
if (x == fa[x])
return x;
else {
fa[x] = find(fa[x]); //路径压缩+按秩合并有些时候可能并不适合
return fa[x];
// return find(fa[x]);
}
}
inline void merge(int i, int j) {
int x = find(i), y = find(j); //先找到两个根节点
if (Rank[x] <= Rank[y])
fa[x] = y;
else
fa[y] = x;
if (Rank[x] == Rank[y] && x != y)
Rank[y]++; //如果深度相同且根节点不同,则新的根节点的深度+1
}
struct Edge {
int u, v, w;
} edge[MAXN];
bool cmp(Edge e1, Edge e2) {
return e1.w < e2.w;
}
int cnt = 0;
int n;
int x, y, m, z, ans = 0;
int kruskal() {
sort(edge, edge + m, cmp);
init(n);
int u, v, w;
for (int i = 0; i < m; ++i) {
u = edge[i].u;
v = edge[i].v;
w = edge[i].w;
if (find(u) == find(v))continue;
merge(u, v);
ans += w;
cnt++;
if (cnt == n - 1)break;
}
if (cnt == n - 1)return ans;
else
return -1;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> x >> y >> z;
edge[i].u = x;
edge[i].v = y;
edge[i].w = z;
}
int res = kruskal();
if (res == -1) { print("orz"); } else print(res);
}
最后更新于