【vijos1234】口袋的天空

problem

solution

codes

#include<iostream>
#include<algorithm>
using namespace std;
struct side{ int u, v, w; }e[10010];
bool cmp(const side &a, const side &b){ return a.w<b.w; }
int fa[10010];
int find(int x){ return x==fa[x] ? x: fa[x]=find(fa[x]);}
int main(){
    int n, m, k;   cin>>n>>m>>k;  
    for(int i = 0; i < m; i++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e, e+m, cmp);
    int cc = n-k, ans = 0;
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 0; i < m; i++){
        if(find(e[i].u) != find(e[i].v)){
            ans += e[i].w;  
            fa[find(e[i].u)] = find(e[i].v);
            cc--;
        }
        if(!cc)break;
    }
    cout<<ans;
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80530615