代码:
#include<iostream>
#include<algorithm>
#define re register
using namespace std;
const int N = 1e6 + 5;
int n,m,k,ans,cnt;
int fa[N];
struct node{
int x,y,w;
}a[N];
inline int find(int x){
if(x == fa[x]){
return x;
}else{
return fa[x] = find(fa[x]);
}
}
inline bool cmp(node a,node b){
return a.w < b.w;
}
inline void cs(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main(){
cs();
cin>>n>>m>>k;
for(re int i = 1;i <= n;i ++){
fa[i] = i;
}
for(re int i = 1;i <= m;i ++){
int x,y,l;
cin>>x>>y>>l;
a[i].x = x;
a[i].y = y;
a[i].w = l;
}
sort(a + 1,a + m + 1,cmp);
for(re int i = 1;i <= n;i ++){
int x = find(a[i].x);
int y = find(a[i].y);
if(x != y){
fa[x] = y;
ans += a[i].w;
cnt ++;
if(cnt >= n - k){
cout<<ans<<"\n";
return 0;
}
}
}
cout<<"No Answer\n";
return 0;
}
第54行,cnt >= n - k是什么意思?怎么来的?为什么这个条件为真时,就可输出答案?
这个是自己一通乱试试出来的,没搞懂