@Python间谍！没问题
2026-02-07 14:37:14
发布于：上海
12阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int fa[209], n, w, num[209];
struct node {
int u, v, w, id;
}a[6009];
bool cmp(node A, node B) {
return A.w < B.w;
}
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
void solve(int up) {
for (int i = 1; i <= n; i++) fa[i] = i, num[i] = 0;
int ans = 0;
for (int i = 0; i < w; i++) {
if (a[i].id > up) continue;
if (get(a[i].u) == get(a[i].v)) continue;
merge(a[i].u, a[i].v);
ans += a[i].w;
}
for (int i = 1; i <= n; i++) num[get(i)]++;
for (int i = 1; i <= n; i++) {
if (num[i] == n) {
cout << ans << '\n';
return;
}
}
cout << -1 << '\n';
}
int main() {
cin >> n >> w;
for (int i = 0; i < w; i++) {
cin >> a[i].u >> a[i].v >> a[i].w;
a[i].id = i;
}
sort(a, a + w, cmp);
for (int i = 0; i < w; i++) solve(i);
return 0;
}
有帮助，赞一个