例题:P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Kruskal
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
struct UFS {
int sz;
vector<int> rank, p;
void link(int x, int y) {
if (x == y)
return;
if (rank[x] > rank[y])
p[y] = x;
else
p[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
void init(int n) {
sz = n;
rank.resize(n + 1);
p.resize(n + 1);
for (int i = 0; i <= sz; i++) {
p[i] = i;
rank[i] = 0;
}
}
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
void unin(int x, int y) {
link(find(x), find(y));
}
void compress() {
for (int i = 0; i < sz; i++)
find(i);
}
};
//种类并查集 merge(y + n, x),merge(x + n, y)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, PII>> e;
for (int i = 0; i < m; i ++) {
int u, v, w;
cin >> u >> v >> w;
e.emplace_back(w, PII(u, v));
}
sort(e.begin(), e.end());
UFS ufs;
ufs.init(n);
i64 ans = 0;
for (int i = 0; i < m; i ++) {
auto [w, uv] = e[i];
auto [u, v] = uv;
if (ufs.find(u) != ufs.find(v)) {
ufs.unin(u, v);
ans += w;
}
}
int op = ufs.find(1);
for (int i = 1; i <= n; i ++) {
if (ufs.find(i) != op) {
cout << "orz" << '\n';
return 0;
}
}
cout << ans << '\n';
return 0;
}
Prim
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector g(n + 1, vector<PII>());
vector<int> dis(n + 1);
vector<bool> vis(n + 1);
i64 ans = 0, cnt = 0;
for (int i = 0; i < m; i ++) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
priority_queue<PII, vector<PII>, greater<PII>> Q;
Q.push({0, 1});
while (Q.size()) {
auto [w, u] = Q.top();
Q.pop();
if (vis[u]) continue;
vis[u] = true;
ans += w;
cnt ++;
dis[u] = w;
for (auto [v, d] : g[u]) {
if (!vis[v]) {
Q.push({d, v});
}
}
}
if (cnt != n) {
cout << "orz\n";
} else
cout << ans << '\n';
return 0;
}