SHARE
TWEET

Untitled

a guest Mar 24th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <fstream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <numeric>
  6.  
  7. using namespace std;
  8.  
  9. std::vector<short> id;
  10.  
  11. inline short root(short &i) {
  12.     while (i != id[i]) {
  13.         id[i] = id[id[i]];
  14.         i = id[i];
  15.     }
  16.     return i;
  17. }
  18.  
  19. int main() {
  20.     std::ifstream fin("spantree2.in");
  21.     std::ofstream fout("spantree2.out");
  22.     std::ios_base::sync_with_stdio(false);
  23.     fin.tie(nullptr);
  24.  
  25.     short n;
  26.     short x, y;
  27.     int w, m;
  28.     std::vector<std::pair<int, std::pair<short, short>>> adj;
  29.  
  30.     int mst = 0;
  31.  
  32.     fin >>n>>m;
  33.     n += 1;
  34.  
  35.     while (fin >>x >> y >> w)
  36.     {
  37.         adj.emplace_back(w, std::make_pair(x, y));
  38.     }
  39.  
  40.     id.resize(n);
  41.     std::iota(id.begin(), id.end(), 0);
  42.  
  43.  
  44.     stable_sort(adj.begin(), adj.end());
  45.  
  46.     int parent1, parent2;
  47.     std::vector<int> sz(n, 1);
  48.  
  49.     for (const auto &edge : adj) {
  50.         short src = edge.second.first;
  51.         short dest = edge.second.second;
  52.         if (root(src) != root(dest)) {
  53.             mst += edge.first;
  54.  
  55.             if (src == dest)
  56.                 continue;
  57.  
  58.             parent1 = root(src);
  59.             parent2 = root(dest);
  60.  
  61.             if (parent1 == parent2)
  62.                 continue;
  63.  
  64.             if (sz[parent1] < sz[parent2])
  65.                 std::swap(parent1, parent2);
  66.  
  67.             id[parent2] = parent1;
  68.             sz[parent1] += sz[parent2];
  69.  
  70.         }
  71.     }
  72.  
  73.     fout << mst;
  74.  
  75.     fin.close();
  76.     fout.close();
  77.     return 0;
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top