Advertisement
scottish_esquire

Задача №2. Вес компоненты

May 26th, 2022
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <fstream>
  6.  
  7.  
  8. /*
  9. Наш тест:
  10.  
  11. 6 10
  12. 2 1
  13. 1 1 2 1
  14. 2 1
  15. 1 2 4 2
  16. 2 1
  17. 1 1 4 3
  18. 2 1
  19. 1 3 5 3
  20. 2 5
  21. 2 6
  22. */
  23.  
  24. struct dsu {
  25.     int n = 0;
  26.     std::vector<int> p;
  27.     std::vector<int> w;
  28.     dsu(int n) {
  29.         p.resize(n); // вектор корней деревьев
  30.         w.resize(n, 0); // вектор суммы весов рёбер
  31.         std::iota(p.begin(), p.end(), 0); // задаёт возрастающую последовательность
  32.     }
  33.     int find1(int v) {
  34.         int r = v;
  35.         while(r != p[r]) {
  36.             r = p[r];
  37.         }
  38.         while (v != p[v]) {
  39.             int next = p[v];
  40.             p[v] = r;
  41.             v = next;
  42.         }
  43.         return v;
  44.     }
  45.     int find2(int v) { // данная функция просто возвращает сумму рёбер, уже известного нам корня
  46.         int r = v;
  47.         int ves = w[v];
  48.         return ves;
  49.     }
  50.     void merge(int a, int b, int ves) {
  51.         w[find1(b)] += w[find1(a)]; // ошибка была в этих двух строках
  52.         p[find1(a)] = find1(b); // ошибка была в этих двух строках
  53.         w[find1(b)] += ves;
  54.     }
  55.     void add(int a, int b, int ves) { // метод добавления ребра
  56.         if (p[find1(a)] != p[find1(b)]) { // мы смотрим, лежат ли наши вершины в одной компоненте связности
  57.             merge(a, b, ves);
  58.         } else {
  59.             w[find1(a)] += ves;
  60.         }
  61.     }
  62. };
  63.  
  64. int main() {
  65.     std::ofstream fout("output.txt");
  66.     std::ios_base::sync_with_stdio(false);
  67.     std::cin.tie(NULL);
  68.     int n = 0, m = 0, a = 0, b = 0, ves = 0, c = 0; // нумерация начинается с 1
  69.     std::cin >> n >> m;
  70.     dsu d = dsu(n);
  71.     for(int i = 0; i < m; i++) {
  72.         std::cin >> c;
  73.         if (c == 1) { // команда на добавление ребра
  74.             std::cin >> a >> b >> ves;
  75.             a--, b--;
  76.             d.add(a, b, ves);
  77.         } else { // команда на просмотр общего веса компоненты связности данной вершины
  78.             std::cin >> a;
  79.             a--;
  80.             int root = d.find1(a); // мы должны найти корень вершины, а затем найти уже вес
  81.             fout << d.find2(root) << std::endl;
  82.         }
  83.     }
  84.     fout.close();
  85.     return 0;
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement