10分求助
查看原帖
10分求助
539495
what_else楼主2022/4/26 13:28

萌新不知道哪里错了,10分

#include<bits/stdc++.h>
using namespace std;
int fa[2000],m,n,num;
struct nid{
    int x,y,t;
}s[100010];
bool bmp(nid a,nid b){
    return a.t<b.t;
}
int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
void uns(int r1,int r2){
    fa[r2]=r1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>s[i].x>>s[i].y>>s[i].t;
    }
    sort(s+1,s+n+1,bmp);
    for(int j=1;j<=m;j++){
        int r1=find(s[j].x);
        int r2=find(s[j].y);
        if(r1!=r2){
            uns(r1,r2);
            num++;
        }
        if(num==n-1){
           printf("%d",s[j].t);return 0; 
        }
    }
    cout<<"-1";
}
2022/4/26 13:28
加载中...