North_encounter @ 2023-08-22 10:25:26
#include<bits/stdc++.h>
using namespace std;
int fa[1000001];
int n,q;
int ans;
struct student {
int u,v,w;
} m[1140514];
int cnt=0;
inline void chu() {
for(int i=1; i<=n; i++) {
fa[i]=i;
}
}
inline int find(int k) {
if(fa[k]==k) return k;
return fa[k]=find(fa[k]);
}
inline bool cmp(student a,student b) {
return a.w<b.w;
}
inline void kruskal() {
sort(m+1,m+q+1,cmp);
for(int i=1; i<=q; i++) {
if(find(m[i].u)==find(m[i].v)) continue;
ans+=m[i].w;
fa[m[i].v]=fa[m[i].u];
if(++cnt>=n-1) {
return;
}
}
if(cnt<n-1) {
ans=-1;
}
return;
}
int main() {
cin>>n>>q;
for(int i=1; i<=q; i++) {
cin>>m[i].u>>m[i].v>>m[i].w;
}
chu();
kruskal();
if(ans==-1){
cout<<"orz";
}
else {
cout<<ans;
}
return 0;
}
by Iniaugoty @ 2023-08-22 10:46:05
@yhliuhao 并查集合并写错了
fa[m[i].v]=fa[m[i].u];
改成
fa[find(m[i].v)] = find(m[i].u);
by North_encounter @ 2023-08-22 10:48:42
@gty314159 已解决,感谢