fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. #define MAX 1000012
  7.  
  8. using namespace std;
  9.  
  10. struct edge{
  11.        int u, v, w;
  12.        edge(){}
  13.        edge(int _u, int _v, int _w){
  14.                 u = _u;
  15.                 v = _v;
  16.                 w = _w;
  17.  
  18.        }
  19. };
  20.  
  21. bool cmp(edge a, edge b){
  22.      return a.w < b.w;     
  23. }
  24.  
  25. int parentof[MAX];
  26.  
  27. void init(){
  28.      for(int i = 0; i < MAX; ++i) parentof[i] = i;     
  29. }
  30.  
  31. int root(int a){
  32.     if (a == parentof[a]) return a;
  33.     return parentof[a] = root(parentof[a]);
  34. }
  35.  
  36. void unite(int a, int b){
  37.      a = root(a);
  38.      b = root(b);
  39.  
  40.      parentof[a] = b;
  41. }
  42.  
  43. int T;
  44. int n, m, k;
  45. int u, v, w;
  46. int main(){
  47.     scanf("%d", &T);
  48.  
  49.     while(T--){
  50.                scanf("%d %d %d", &n, &m, &k);
  51.                vector<edge> E;
  52.  
  53.                for(int i = 0; i < m; ++i){
  54.                        scanf("%d %d %d", &u, &v, &w);
  55.                        E.push_back(edge(u, v, w));
  56.                }
  57.  
  58.                sort(E.begin(), E.end(), cmp);
  59.  
  60.                int SUM = 0;
  61.                int groupN = n;
  62.  
  63.                init();
  64.  
  65.                for(int i = 0; i < E.size(); ++i){
  66.                        if(root(E[i].u) != root(E[i].v)){
  67.                                        //cout << E[i].u << " " << E[i].v << endl;
  68.                                        unite(E[i].u, E[i].v); 
  69.                                        SUM += E[i].w;
  70.                                        --groupN;        
  71.                        }
  72.                        if(groupN <= k) break;
  73.                }
  74.                if(groupN > k){
  75.                          printf("%d\n", -1);          
  76.                } else {
  77.                          printf("%d\n", SUM);
  78.                }
  79.     }
  80.  
  81.     //getchar();
  82.     //getchar();
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0s 7248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ypHFjP
http://f...content-available-to-author-only...s.org/thread-556-1-1.html
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!