fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1e6+5;
  4. const int mod = 1e9 + 7;
  5. const int oo = 1e18+5;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, pair<int, int>> iii;
  8. #define fi first
  9. #define se second
  10. #define read(_a, n) for(int i = 1; i <= n; i++) cin >> _a[i]
  11. #define For(i, _a, _b) for(int i = _a; i <= _b; i++)
  12. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  13. #define File(_x,_y) if (fopen(_x, "r")) freopen(_x, "r", stdin)//,freopen(_y, "w", stdout)
  14. #define file "main"
  15. #define bit(x, i) ((x >> i) & 1)
  16. #define bat(x, i) (x  (1 << i))
  17.  
  18. int n, m, c, res, cnt;
  19. bool check[maxn];
  20. vector<ii> adj[maxn];
  21. iii e[maxn];
  22.  
  23. void dfs(int u)
  24. {
  25.     check[u] = 1;
  26.     for(int i = 0; i < adj[u].size(); i++)
  27.     {
  28.         int v = adj[u][i].fi;
  29.         if(!check[v]) dfs(v);
  30.     }
  31. }
  32.  
  33. int32_t main()
  34. {
  35.     fastIO;
  36.     File(file ".inp", file ".out");
  37.  
  38.     cin >> n >> m;
  39.     for(int i = 1;i <= m; i++)
  40.     {
  41.         cin >> e[i].se.fi >> e[i].se.se >> e[i].fi;
  42.         adj[e[i].se.fi].push_back({e[i].se.se , e[i].fi});
  43.         adj[e[i].se.se].push_back({e[i].se.fi , e[i].fi});
  44.     }
  45.     for(int i = 1;i <= n; i++)
  46.     if(!check[i]) dfs(i), cnt++;
  47.     sort(e+1, e+m+1);
  48.     c =cnt;
  49.     for(int i = 1; i<= m;i++)
  50.     {
  51.          if(c==1)break;
  52.         res += e[i].fi;
  53.         c--;
  54.     }
  55.     cout << res;
  56. }
  57.  
Success #stdin #stdout 0.01s 29180KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FVFvr2
language:
C++14 (gcc 8.3)
created:
3 days 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!