fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl '\n'
  5. #define inf32 ((int)1e9 + 7)
  6. #define inf64 ((long long)1e18 + 7)
  7. #define MASK32(x) (1 << (x))
  8. #define MASK64(x) (1ll << (x))
  9. #define BIT(mask, i) (((mask) >> (i)) & 1)
  10. #define all(a) begin(a), end(a)
  11. #define isz(a) ((int)a.size())
  12.  
  13. const int N = 2e5 + 1;
  14.  
  15. struct Edge {
  16.     int u, v, w;
  17. } e[N];
  18. vector<int> g[N];
  19. int comp[N];
  20. bool cycle[N];
  21.  
  22. struct DSU {
  23.     vector<int> lab;
  24.  
  25.     DSU(int n) : lab(n + 1, -1) {}
  26.  
  27.     int find_set(int u) {
  28.         return (lab[u] < 0) ? u : (lab[u] = find_set(lab[u]));
  29.     }
  30.  
  31.     bool union_sets(int u, int v) {
  32.         u = find_set(u);
  33.         v = find_set(v);
  34.         if(u == v) return 0;
  35.         if(lab[u] > lab[v]) swap(u, v);
  36.         lab[u] += lab[v];
  37.         lab[v] = u;
  38.         return 1;
  39.     }
  40. };
  41.  
  42. void dfs(int u, int r) {
  43.     comp[u] = r;
  44.     for(int i : g[u]) {
  45.         int v = u ^ e[i].u ^ e[i].v;
  46.         if(!comp[v]) dfs(v, r);
  47.     }
  48. }
  49.  
  50. int main() {
  51.     ios_base::sync_with_stdio(0);
  52.     cin.tie(0);
  53.  
  54.     int n, m;
  55.     cin >> n >> m;
  56.     for(int i = 1, u, v, w; i <= m; ++i) {
  57.         cin >> e[i].u >> e[i].v >> e[i].w;
  58.         g[e[i].u].push_back(i);
  59.         g[e[i].v].push_back(i);
  60.     }
  61.     for(int u = 1; u <= n; ++u)
  62.         if(!comp[u]) dfs(u, u);
  63.     sort(e + 1, e + m + 1, [](const Edge& lhs, const Edge& rhs) {
  64.         return lhs.w > rhs.w;
  65.     });
  66.     DSU dsu(n);
  67.     long long res = 0;
  68.     for(int i = 1; i <= m; ++i) {
  69.         if(dsu.union_sets(e[i].u, e[i].v)) res += e[i].w;
  70.         else if(!cycle[comp[e[i].u]]) {
  71.             res += e[i].w;
  72.             cycle[comp[e[i].u]] = 1;
  73.         }
  74.     }
  75.     cout << res;
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 9676KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/scbff3
language:
C++14 (gcc 8.3)
created:
10 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!