SHARE
TWEET

Untitled

a guest Jan 12th, 2017 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <fstream>
  4. using namespace std;
  5. const int maxn = 1e5;
  6. int ranks[maxn];
  7. int parent[maxn];
  8. struct edge {
  9.     int from, to, w;
  10.     edge(int a = 0, int b = 0, int c = 0) {
  11.         from = a;
  12.         to = b;
  13.         w = c;
  14.     }
  15.     bool operator<(edge a) {
  16.         return a.w > w;
  17.     }
  18. };
  19. void make_set(int v) {
  20.     ranks[v] = 0;
  21.     parent[v] = v;
  22. }
  23. int find_set(int v) {
  24.     if(parent[v] == v) return v;
  25.     return parent[v] = find_set(parent[v]);
  26. }
  27. void onion_set(int a, int b) {
  28.     a = find_set(a);
  29.     b = find_set(b);
  30.     if (a != b) {
  31.        if (ranks[a] < ranks[b]) swap(a, b);
  32.         parent[b] = a;
  33.         if (ranks[a] == ranks[b]) ranks[a]++;
  34.     }
  35. }
  36. edge e[maxn];
  37. int main() {
  38.     int n,m, ans = 0;
  39.     ifstream in("spantree2.in");
  40.     ofstream out("spantree2.out");
  41.     in >> m >> n;
  42.     for(int i = 0; i < m; i++) {
  43.         make_set(i + 1);
  44.     }
  45.     for(int i = 0; i < n; i++) {
  46.         int a, b, c;
  47.         in >> a >> b >> c;
  48.         e[i] = edge(a, b, c);
  49.     }
  50.     sort(e, e + n);
  51.     for(int i = 0; i < n; i++) {
  52.         int v = e[i].from;
  53.         int u = e[i].to;
  54.         int w = e[i].w;
  55.         if (find_set(v) != find_set(u)) {
  56.             ans += w;
  57.             onion_set(v, u);
  58.         }
  59.     }
  60.     out << ans;
  61.     return 0;
  62. }
RAW Paste Data
Top