@Python间谍！没问题

Jason_

2026-02-07 14:37:14

发布于：上海

11阅读

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;  
}

有帮助，赞一个

去预览

0/2000

全部评论 1

王天衍
我也搞Python。

2026-02-07 来自江西
0

全部评论 1

热门讨论