Задача
В связном графе найдите остовное дерево минимального веса.
Входные данные
Первая строка содержит два натуральных числа $n$ и $m$ $($$1 \leqslant n \leqslant 20000$, $0 \leqslant m \leqslant 100000$$)$ — количество вершин и рёбер графа соответственно. Следующие $m$ строк содержат описания рёбер по одному в строке. Ребро номер $i$ описывается тремя натуральными числами $b_i$, $e_i$ и $w_i$ $($$1 \leqslant b_i$, $e_i \leqslant n$, $0 \leqslant w_i \leqslant 100000$$)$ — номера концов ребра и его вес соответственно.
Граф является связным.
Выходные данные
Выведите единственное целое число — вес минимального остовного дерева.
Тесты
| Входные данные | Выходные данные |
| 4 4 1 2 1 2 3 2 3 4 5 4 1 4 |
7 |
| 10 10 1 3 1 1 4 5 1 2 6 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 6 4 2 6 5 6 |
15 |
| 7 12 1 2 20 1 7 1 1 6 23 6 7 36 2 7 4 2 3 15 7 3 9 6 5 28 7 5 25 3 4 3 4 5 17 4 7 16 |
57 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> #include <vector> #include <algorithm> #include <utility> using namespace std; int get(const int &n, int *&subtree) { if (subtree[n] == n) return n; return subtree[n] = get(subtree[n], subtree); } void merge(const int &a, const int &b, int *&subtree, int *&vertex_rank) { int ra = get(a, subtree), rb = get(b, subtree); if (vertex_rank[ra] < vertex_rank[rb]) subtree[ra] = rb; else if (vertex_rank[rb] < vertex_rank[ra]) subtree[rb] = ra; else { subtree[ra] = rb; vertex_rank[rb]++; } } int main() { int vertices, edges; scanf("%i%i", &vertices, &edges); vector <pair<int, pair<int, int>>> v(edges); for (int i = 0; i < edges; ++i) { scanf("%i%i%i", &v[i].second.first, &v[i].second.second, &v[i].first); } sort(v.begin(), v.end()); int *subtree = new int[vertices]; int *vertex_rank = new int[vertices]; for (int i = 0; i < vertices; i++) { subtree[i] = i; vertex_rank[i] = 1; } int spanning_tree_weight = 0; for (int i = 0; i < edges; ++i) { if (get(v[i].second.first - 1, subtree) != get(v[i].second.second - 1, subtree)) { spanning_tree_weight += v[i].first; merge(v[i].second.first - 1, v[i].second.second - 1, subtree, vertex_rank); } } printf("%i", spanning_tree_weight); delete[] subtree; delete[] vertex_rank; return 0; } |
Решение задачи
Алгоритм
Задача решается алгоритмом Краскала. Для хранения данных удобно использовать вектор пар (одна пара = одна строка ввода). Пары в свою очередь состоят из двух элементов: пара вершин и вес ребра. Алгоритм Краскала предполагает сортировку рёбер по весу в порядке неубывания. Затем каждой вершине графа ставится в соответствие собственное поддерево. Удобно это сделать с помощью массива, элементов массива будет столько же, сколько и вершин. Далее нужно пройтись по всем рёбрам в порядке неубывания и определить, принадлежат ли вершины ребра $i$ одному и тому же поддереву. Если вершины находятся в разных поддеревьях, то эти поддеревья объединяются, а вес данного ребра дописывается в ответ.
Оптимизация
При помощи простого массива или вектора задача выполняется со сложностью $O(M log N + N^2)$, где $N$ — количество вершин, $M$ — количество рёбер. Система непересекающихся множеств (СНМ) позволяет добиться сложности $O(M log N)$. При поиске элемента в СНМ необходимо лишь подниматься вверх по деревьям, поэтому достаточно хранить для каждой вершины только номер её прямого предка. Для этого используется массив $subtree$. Для задания множества используется номер вершины — корня соответствующего дерева. Поэтому чтобы определить, принадлежат ли два элемента к одному и тому же множеству, для каждого элемента нужно найти корень соответствующего дерева (поднимаясь вверх пока это возможно) и сравнить эти корни. При поиске корня заданной вершины будем переподвешивать её за найденный корень при выходе из рекурсивной функции $get$. Пусть нам нужно объединить $(merge)$ множества с корнями $a$ и $b$. Присвоим $p[a]=b$, тем самым подвесив всё дерево $a$ к корню дерева $b$. Одна из самых простых и эффективных оптимизаций — поддерживать для всех деревьев текущую глубину, и при объединении подвешивать дерево с меньшей глубиной к корню дерева с большей глубиной. Глубина дерева данной вершины хранится в виде её ранга (массив $vertex$_$rank$).
Очень хорошо, молодец.
Я правда не понял зачем вы вводите каждую переменную отдельной командой.
Моя реализация этого подхода очень похожа и работает с той же скоростью (с точностью до операторов ввода-вывода), но несколько компактнее.
Спасибо, сократила ввод переменных до одной команды. Интересно, что scanf() и cin работают с одинаковой скоростью.
Вы ошибаетесь. Ваше решение со scanf() заходит за 28 msk, а использование cin затягивает дело до 112. Ускорить работу можно отключив синхронизацию ввода и вывода.