下面是完整的 C++ 代码实现,主要使用了 Kruskal 算法。
时间复杂度为 O(mlogm),其中 m 是边数。
下面是完整的 C++ 代码实现:
cpp#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100010;
const int MAXM = 200010;
int n, m;
int p[MAXN], rank[MAXN];
struct Edge {
int u, v, w;
} e[MAXM];
bool cmp(const Edge& a, const Edge& b) {
return a.w < b.w;
}
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) swap(x, y);
p[y] = x;
if (rank[x] == rank[y]) ++rank[x];
}
int kruskal() {
sort(e, e + m, cmp);
for (int i = 1; i <= n; ++i) {
p[i] = i;
rank[i] = 0;
}
int res = 0, cnt = 0;
for (int i = 0; i < m; ++i) {
if (cnt == n - 1) break;
int u = e[i].u, v = e[i].v, w = e[i].w;
if (find(u) == find(v)) continue;
unite(u, v);
res += w;
++cnt;
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[i] = {u, v, w};
}
printf("%d\n", kruskal());
return 0;
}
|