СНМ¶
СНМ - система непересекающихся множеств
Эта структура данных предоставляет следующие возможности. Изначально имеется несколько элементов, каждый из которых находится в отдельном (своём собственном) множестве. За одну операцию можно:
- \(join\_set(x, y)\) - объединяет два указанных множества (множество, в котором находится элемент \(x\), и множество, в котором находится элемент \(y\)).
- \(find\_set(x, y)\) - возвращает, в каком множестве находится указанный элемент \(x\).
Построение эффективной структуры данных
Множества элементов мы будем хранить в виде деревьев: одно дерево соответствует одному множеству. Корень дерева — это представитель (лидер) множества. При реализации это означает, что мы заводим массив parent, в котором для каждого элемента мы храним ссылку на его предка в дерева. Для корней деревьев будем считать, что их предок — они сами (т.е. ссылка зацикливается в этом месте).
int find_set(int v) {
if (v == p[v])
return v;
return find_set(p[v]);
}
void join_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b)
p[b] = a;
}
int main() {
...............
p.resize(n);
std::iota(p.begin(), p.end(), 0);
}
Внимание
\(find\_set() - O(n)\)
Легко построить пример, когда после нескольких объединений множеств получится ситуация, что множество — это дерево, выродившееся в длинную цепочку.
В результате каждый вызов \(find\_set()\) за длину дерева \(O(n)\).
Эвристика сжатия пути¶
Подсказка
\(find\_set() - O(log n)\)
\(join\_set() - O(2 * find\_set())\)
Она заключается в том, что когда после вызова \(find\_set(v)\) мы найдём искомого лидера \(p\) множества, то запомним, что у вершины \(v\) и всех пройденных по пути вершин — именно этот лидер \(p\).
\(parent[]\) - теперь это сжатый массив предков, хранит предок предка, предок предка предка, и т.д.
int find_set(int v) {
if (v == p[v])
return v;
return p[v] = find_set(p[v]);
}
Эвристика объединения по рангу¶
Подсказка
При выполнении \(join\_set()\) будем присоединять дерево с меньшим рангом к дереву с большим рангом.
bool join(ll u, ll v) {
u = get(u);
v = get(v);
if (u == v) {
return false;
}
if (r[u] > r[v]) {
swap(u, v);
}
p[u] = v;
r[v] = max(r[v], r[u] + 1);
return true;
}
Объединение эвристик: сжатие пути плюс ранговая эвристика
Окончательный результат таков: при совместном применении эвристик сжатия пути и объединения по рангу время работы на один запрос получается \(O (\alpha(n)\).
\(\alpha(n)\) — обратная функция Аккермана (n ~ 4, n <= 100 ** 600)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18
vector<ll> p, r;
ll get(ll u) {
if (p[u] == u)
return u;
return p[u] = get(p[u]);
}
bool join(ll u, ll v) {
u = get(u);
v = get(v);
if (u == v) {
return false;
}
if (r[u] > r[v]) {
swap(u, v);
}
p[u] = v;
r[v] = max(r[v], r[u] + 1);
return true;
}
int main() {
ll n, m, a, b, w;
cin >> n >> m;
p.resize(n);
for (int i = 0; i < n; i++) {
p[i] = i;
}
r.resize(n);
vector<pair<ll, pair<ll, ll>>> e(m);
for (int i = 0; i < m; i++) {
cin >> a >> b >> w;
a--, b--;
e[i] = {w, {a, b}};
}
sort(e.begin(), e.end());
ll ans = 0;
ll k = 0;
for (int i = 0; i < m; i++) {
auto t = join(e[i].second.first, e[i].second.second);
if (t) {
ans = e[i].first;
k++;
}
if (k == n - 1) {
break;
}
}
cout << ans;
return 0;
}
Остовное дерево.¶
Остовное дерево графа состоит из минимального подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрам.
Минимальное остовное дерево - остовное дерево при этом обладающие наименьшим возможным весом.
\(O(M\log N)\) Минимальное остовное дерево. Алгоритм Крускала с системой непересекающихся множеств¶
- Отсортируем все рёбра по неубыванию веса
- Затем поместим каждую вершину в своё дерево (т.е. своё множество) - на это уйдёт в сумме \(O(N)\)
- Перебираем все рёбра (в порядке сортировки) и для каждого ребра за \(O(1)\) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов find_set() за \(O(1)\)). Наконец, объединение двух деревьев будет осуществляться вызовом join_set() - также за \(O(1)\).
Итого мы получаем асимптотику \(O (M log N + N + M) = O (M log N)\).
TODO CODE
\(O(M\log N)\) Минимальное остовное дерево. Алгортим прима.¶
Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое, \(n-1\) ребро).
В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше \(n-1\)).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18
vector<bool> used;
vector<double> min_;
vector<int> sel_;
vector<ll> d;
vector<pair<ll, ll>> z;
ll n;
double ans = 0;
double get(ll f, ll s) {
return sqrt((z[f].first - z[s].first) * (z[f].first - z[s].first) + (z[f].second - z[s].second) * (z[f].second - z[s].second));
}
void prim() {
min_[0] = 0;
for (int i = 0; i < n; ++i) {
int v = -1;
for (int j = 0; j < n; j++)
if (!used[j] && (v == -1 || min_[j] < min_[v]))
v = j;
used[v] = true;
ans += min_[v];
for (int to = 0; to < n; to++)
if (get(v, to) < min_[to]) {
min_[to] = get(v, to);
sel_[to] = v;
}
}
}
int main() {
cin >> n;
d.resize(n);
used.resize(n);
min_.assign(n, INF), sel_.assign(n, -1);
z.resize(n);
for (int i = 0; i < n; i++) {
cin >> z[i].first >> z[i].second;
}
prim();
cout << setprecision(10) << ans;
return 0;
}