测试点提交记录

Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int n,m,k,u,v,w,ans,cnt;
struct node{
    int x,y,v;
}a[maxn];
int fa[maxn];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
    return x.v>y.v;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        a[i].x=u,a[i].y=v,a[i].v=w;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx!=fy){
            cnt++;
            fa[fx]=fy;
            ans+=a[i].v;
            if(cnt==k) break;
        }
    }
    printf("%d",ans);
    return 0;
}