- 题解
什么是快乐星球
- @ 2026-8-3 11:44:01
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
struct node{
int x, y, w;
}e[N];
int f[N], n, m;;
bool cmp(node a, node b){
return a.w < b.w;
}
int get(int x){
if(f[x] == 0) return x;
return f[x] = get(f[x]);
}
void merge(int x, int y){
x = get(x), y = get(y);
f[x] = y;
}
void Kruskal(){
int cnt = 0, s = 0;
for(int i = 1; i <= m; i++){
int x = e[i].x, y = e[i].y, w = e[i].w;
if(get(x) != get(y)){
merge(x, y);
cnt++;
s += w;
if(cnt == n-1) break;
}
}
if(cnt == n-1) cout << s;
else cout << "Not QwQ";
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> e[i].x >> e[i].y >> e[i].w;
}
sort(e + 1, e + 1 + m, cmp);
Kruskal();
return 0;
}
0 条评论
目前还没有评论...