Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <numeric>
- #include <fstream>
- /*
- Наш тест:
- 6 10
- 2 1
- 1 1 2 1
- 2 1
- 1 2 4 2
- 2 1
- 1 1 4 3
- 2 1
- 1 3 5 3
- 2 5
- 2 6
- */
- struct dsu {
- int n = 0;
- std::vector<int> p;
- std::vector<int> w;
- dsu(int n) {
- p.resize(n); // вектор корней деревьев
- w.resize(n, 0); // вектор суммы весов рёбер
- std::iota(p.begin(), p.end(), 0); // задаёт возрастающую последовательность
- }
- int find1(int v) {
- int r = v;
- while(r != p[r]) {
- r = p[r];
- }
- while (v != p[v]) {
- int next = p[v];
- p[v] = r;
- v = next;
- }
- return v;
- }
- int find2(int v) { // данная функция просто возвращает сумму рёбер, уже известного нам корня
- int r = v;
- int ves = w[v];
- return ves;
- }
- void merge(int a, int b, int ves) {
- w[find1(b)] += w[find1(a)]; // ошибка была в этих двух строках
- p[find1(a)] = find1(b); // ошибка была в этих двух строках
- w[find1(b)] += ves;
- }
- void add(int a, int b, int ves) { // метод добавления ребра
- if (p[find1(a)] != p[find1(b)]) { // мы смотрим, лежат ли наши вершины в одной компоненте связности
- merge(a, b, ves);
- } else {
- w[find1(a)] += ves;
- }
- }
- };
- int main() {
- std::ofstream fout("output.txt");
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(NULL);
- int n = 0, m = 0, a = 0, b = 0, ves = 0, c = 0; // нумерация начинается с 1
- std::cin >> n >> m;
- dsu d = dsu(n);
- for(int i = 0; i < m; i++) {
- std::cin >> c;
- if (c == 1) { // команда на добавление ребра
- std::cin >> a >> b >> ves;
- a--, b--;
- d.add(a, b, ves);
- } else { // команда на просмотр общего веса компоненты связности данной вершины
- std::cin >> a;
- a--;
- int root = d.find1(a); // мы должны найти корень вершины, а затем найти уже вес
- fout << d.find2(root) << std::endl;
- }
- }
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement