全WA求助

P3366 【模板】最小生成树

jy20091121 @ 2023-10-11 19:12:25

#include<bits/stdc++.h>
using namespace std;
int fi[213132],n,m,ans,eu,ev;
int cnt =0;
struct re{
    int u,v,w;
}p[1233022];
bool cmp(re x,re y){
    return x.w<y.w;
}
int find(int x){
    while(x!=fi[x]) x=fi[x]=fi[fi[x]];
    return x;
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fi[i]=i; 
    for(int i=1;i<=m;i++){
    cin>>p[i].u>>p[i].v >>p[i].w;
    }
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=m;i++){
    eu=find(p[i].u),ev=find(p[i].v);
    if(eu==ev){
    continue;   
    }
    ans+=p[i].w;
    fi[ev]=eu;
    if(++cnt==n-1) break;
    }
    cout<<ans;
}

求DALAO指点


by small_john @ 2023-10-11 19:14:45

@zhangjiayii sort(p+1,p+1+n,cmp); 改成 sort(p+1,p+1+m,cmp);


by jy20091121 @ 2023-10-11 19:23:03

@pyy1 谢谢DALAO


|