Алгоритм двух китайцев

Постановка задачи

Дан взвешенный ориентированный граф $G(V, E)$, в нем необходимо найти минимальное остовное дерево с заданным корнем.

Определение:
Остовное дерево в ориентированном графе $G(V, E)$ —это такой ациклический подграф нашего графа $G$, что выделена вершина $root -$ корень дерева, и в каждую вершину, кроме $root$, входит ровно одно ребро, а в $root$ не входит ни одного ребра.

Проверка на существование: все вершины должны быть достижимы из корня.

Медленный алгоримт

Для каждой вершины (кроме корня) найдем ребро, которое будет входить в неё в ответе.

1. Для каждой вершины (кроме корня) найдем минимальное ребро, которое в неё входит и вычтем его вес из всех ребер, входящих в неё.
2. В новом графе для каждой врешины (кроме корня) зафиксируем одно ребро нулевого веса, (для ребра мы должны помнить, в какую вершину изначального графа она входила, что бы обновить для этой вершины ответ).
3. Если рассматриваемые на втором шаге ребра образовали дерево, то мы нашли ответ и алгоритм завершается.
4. Если они не образовали дерево, то найдется цикл из данных ребер. Сожмем все циклы в вершины и перейдем к шагу 1.

Сжатие цикла подразумевает, что вместо цикла мы создаем новую вершину, ребра идущие в цикл будут идти в эту вершину, исходящие из цикла будут исходить из данной вершины, а ребра внутри цикла мы просто удалим.

Докажем корректность

Если прибавить ко всем реберам входящим в вершину $v$, не являющуюся корнем, число $x$, то изменится только вес минимального остова, а не набор ребёр. Причем к весу остова также прибавится $x$. Значит преобразование графа на первом шаге алгоритма не влияет на ответ.

(Если в задаче не нужно восстанавливать ответ, то можно не запоминать ребра, а просто поддерживать, на сколько нужно увеличить ответ)

После выполнения 1 шага, веса всех ребер в графе неотрицательные, значит, остовное дерево на ребрах с нулевым весом будет являтся ответом, следовательно 3 шаг алгоритма корректен.

Докажем, что в цикле поменяет свое ребро-ответ только одна вершина, пусть таких вершин хотя бы 2, тогда у одной из них заменим текущий ответ, ребро из цикла, оно имеет вес 0, а значит полученное остовное дереве - не хуже. Следовательно, мы можем заменить весь цикл одной вершиной и найдя ответ в новом графе, узнаем ответ для исходного.

И вообще, данный алгоритм интуитивно понятен.

Оценим время работы

На поиск и сжатие циклов мы тратим $O(E)$ времени. Каждый раз количество вершин в графе уменьшается хотя бы на 1, следовательно, наш алгоритм работает за $O(VE)$

Быстрый алгоритм

Опять же, мы хотим найти входящее ребро в каждую вершину (кроме корня).

• Мы можем сжимать циклы по 1, за размер цикла.
• Сжимать цикл можно неявно, например с помощью снм.
• Нужна структура, которая позволит быстро находить минимальное ребро, вычитать из всех рёбер константу, удалять минимальное ребро (оно может вести из вершины в её саму, после сжатия цикла) и объединять две такие структуры. Для этого подойдет неявное декартово дерево, в котором можно поддерживать минимум и делать спуск или std::set испульзуя переливания от меньшего к большему (что к сожалению даст ассимртотику не $O(log(E))$, а $O(log^2(E))$.

сам алгоритм:

1. Берем вершину, для которой ещё не нашли ответ. Если такой нет, то мы нашли ответ.
2. Выполянем для неё операцию вычитания веса минимального ребра и переходим её "родителя" по ребру с нулевым весом, повтояем для новой рассматриваемой вершины, пока не произойдет один из двух вариантов:
   1. Мы пришли в вершину достижимую из корня, следовательно наша изначальная вершина стала достижимой из корня по нулевым ребрам.
   2. Мы пришли в уже посещенную на данной итерации вершину, следовательно нашли цикл из нулевых ребер. Его необходимо неявно сжать с помощью снм и продолжить идти вверх по нулевым ребрам.

Время работы быстрого алгоритма

Изначально у нас $V$ структур, в которых мы храним ребра, значит сжимать их мы будем $O(V)$ раз, а каждое сжатие происходит за $O(log(E))$ или $O(log^2(E))$. Каждое ребро мы удаляем не более одного раза, смотрим на ребро не более одного раза вычитаем не более O(E) раз. Значит итоговая ассимптотика $- O(E + V log(E))$ или $O(E + V log^2(E))$.

Фрагмент кода на c++

$graph[v] -$ ребра ведущие в $v$

 1 for (ll v = 0; v < n; ++v) {
 2     if (dsu.check(v, 0)) { // проверяем, что вершина ещё недостижима из корня
 3         continue;
 4     }
 5     ++timer; // быстрое обнуление used-а
 6     vector<ll> path; // будем хранить пройденный путь
 7     path.emplace_back(v);
 8     while (!dsu.check(path.back(), 0)) { // проверяем, что ещё не дошли до корня
 9         ll v = dsu.get(path.back()); // берём последнюю вершину пути
10         used[v] = timer;
11         while (dsu.check(graph[v].begin()->second, v)) { 
12             graph[v].erase(graph[v].begin()); // удаляем петли
13         }
14         ll u = dsu.get(graph[v].begin()->second); // получаем следующую вершину пути
15         result += graph[v].begin()->first + delta[v]; // прибавляем к ответу вес ребра
16         delta[v] -= graph[v].begin()->first + delta[v]; // вычитаем из всех ребер ведущих в $v$ вес ребра
17         if (used[u] != timer) {
18             path.emplace_back(u);
19             continue;
20         }
21         while (!dsu.check(path.back(), u)) { // удаляем цикл
22             dsu.merge(path.back(), u); // внутри этой функции я так же объединяю множества рёбер
23             path.pop_back();
24         }
25     }
26     while (!path.empty()) { // проставляем всем посещённым вершинам, что они достижимы из корня
27         dsu.merge(s.back(), 0);
28         path.pop_back();
29     }
30 }

---

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana