10分Kruskal 求救!
查看原帖
10分Kruskal 求救!
891845
liuhaopeng666楼主2023/8/25 09:53
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100010
struct edge{
    int u,v,len;
}e[maxn];
int head[maxn];
int n,m,k;
bool cmp(edge a,edge b){
    return a.len<b.len;
}
int find(int a){
    return (head[a]==a)?a:head[a]=find(head[a]);
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].len;
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++){
        head[i]=i;
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        int x=find(e[i].u);
        int y=find(e[i].v);
        if(x==y) continue;
        ans+=e[i].len;
        head[x]=y;
    }
    if(ans){
        cout<<ans<<endl;
    }
    else{
        cout<<"No Answer"<<endl;
    }
    return 0;
}
2023/8/25 09:53
加载中...