0pts求助
查看原帖
0pts求助
876268
tanzexiaodezhonghao楼主2024/7/17 09:34
#include<bits/stdc++.h>
using namespace std;const int N=3e5+5,M=5e5+5;
struct node{
    int u,v,w;
};
vector<node> G;int n,m,u,v,w;int fa[M];long long ans=0,cnt=1,k;
void init(){for(int i=1;i<=n;i++){fa[i]=i;}}
int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        fa[y] = x;
    }
}
bool cmp(node x,node y){return x.w<y.w;}
int kruskal(){sort(G.begin(),G.end(),cmp);
    for(int i=0;i<m;i++){
        int u=find(G[i].u),v=find(G[i].v);
        if(u==v) continue;
        ans+=G[i].w;
        fa[u]=v;cnt++;
        if(cnt==k) return ans;
    }return -114514;
}
int main(){ios::sync_with_stdio(false);
cin.tie(0);cin>>n>>m>>k;
    init();
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;G.push_back((node){u,v,w});
    }
    long long ta=kruskal();
    if(ta==-114514) cout<<"No Answer";
    else cout<<ta;
    return 0;
}
2024/7/17 09:34
加载中...