Привет, Codeforces!

Несколько дней назад я обнаружил интересный способ определения стоимости второго минимального остовного дерева.

Условие задачи

Вам дан взвешенный граф на $$$n$$$ вершинах и $$$m$$$ рёбрах. Вам нужно построить два остовных дерева: первое остовное дерево должно быть минимальным, а второе также должно иметь минимальную сумму рёбер, но деревья должны различаться хотя бы одним ребром (неформально: первое — MST (Minimum Spanning Tree — Минимальное Остовное Дерево), а второе настолько близко к MST, насколько это возможно).

Я наткнулся на эту задачу больше двух лет назад на кружке по олимпиадному программированию. Там эта задача имела маленькие ограничения на $$$n$$$ и $$$m$$$, которые предполагали решение за $$$O(nm\cdot\alpha(n))$$$ (где $$$\alpha$$$ — обратная функция Аккермана).

Предполагаемое решение

Для начала давайте отсортируем список всех рёбер по их стоимости и найдём MST при помощи алгоритма Крускала. Так как остовные деревья различаются хотя бы одним ребром, то второе остовное дерево не должно содержать как минимум одно ребро первого (иначе бы деревья были одинаковыми). Так что давайте пройдёмся по всем рёбрам MST и для каждого будем предполагать, что оно не входит во второе MST (таким образом, мы попробуем выбросить $$$n - 1$$$ ребро). Теперь нам всего лишь нужно пометить это ребро как бесполезное и запустить стандартный алгоритм Крускала, который пропустит помеченное ребро (нам даже не нужно пересортировывать рёбра, так как их порядок не поменяется). Благодаря этому мы найдём MST без определённого ребра. Самое дешёвое из этих остовных деревьев и будет вторым MST (потому что мы попробовали исключить каждое ребро из первого MST).

Ещё тогда мне показалось странным, что задача с такой простой постановкой не имела быстрого решения, поэтому я начал искать его, но допустил ошибку, которую смог осознать только недавно (полезную информацию об этой задаче я смог найти только после того, как начал писать блог).

Лучшее решение

Однако перед началом решения необходимо сформулировать важную лемму.

Лемма о втором MST

Существует такое второе MST, что оно отличается от первого ровно одним ребром.

Спасибо D_ck за доказательство этой леммы.

По лемме о втором MST нам нужно удалить одно ребро и добавить одно ребро к основному MST, чтобы создать из него второе MST. Так что давайте инвертируем идею медленного решения. Вместо того чтобы искать ребро, которое нам следует удалить, мы будем искать ребро, которое нам следует добавить. Теперь для каждого ребра, которое не содержится в MST (их $$$m - n + 1$$$ штук), мы будем предполагать, что оно содержится во втором MST. Если мы добавим это ребро в дерево, то оно образует цикл с путём между концами нашего ребра. Это означает, что мы должны выкинуть любое ребро на этом пути. Легко убедиться, что граф при этом останется связным. Чтобы минимизировать увеличение стоимости дерева, нам нужно удалить самое дорогое ребро на этом пути (например, оно может быть найдено при помощи двоичных подъёмов: нужно всего лишь предподсчитать максимальный вес ребра на каждом прыжке и найти максимум на обеих половинах пути, разделённых LCA). Таким образом, весь алгоритм работает в три шага.

• Первый шаг. Находим MST любым способом.
• Второй шаг. Предподсчитываем двоичные подъёмы с максимальными рёбрами на остовном дереве.
• Третий шаг. Находим ребро, которое увеличивает ответ наименьшим образом ($$$\Delta_{ans} = e_{new} - e_{old}$$$).

Асимптотическая сложность: $$$O(m\log n) + O(n\log n) + O((m - n)\log n) = O(m\log n)$$$.

Бонус (Количество MST в специфичном графе)

Мой друг показал мне эту задачу несколько дней назад, он нашёл её в отборе в старшие параллели ЛКШ (летней компьютерной школы). Она очень напомнила мне задачу о втором MST, и я наконец решил её с помощью друга после долгого перерыва (вот почему я решил написать про обе задачи в этом блоге).

Условие задачи

Вам дан взвешенный граф на $$$n$$$ вершинах и $$$m$$$ рёбрах, в котором каждый вес встречается не более трёх раз. Вам нужно найти количество минимальных остовных деревьев в этом графе по модулю $$$10^9+7$$$.

Решение

Благодаря доказательству леммы о втором MST (там читайте выделенный жирным текст), легко понять, что каждое MST имеет такое же количество рёбер определённого веса, что и остальные (ведь каждая операция замены ребра добавляет ту же стоимость, что и удаляет).

Теперь давайте рассмотрим каждый вес независимо. Сколько изменений с этим весом мы можем сделать? Сколько вариантов порождают эти изменения? Давайте рассмотрим все случаи:

MST содержит 0 рёбер этого веса

Мы не можем менять рёбра, потому что у нас их просто нет. 0 изменений, 1 вариант.

MST содержит 1 ребро этого веса

Мы можем заменить это ребро на другое, если это возможно. 0/1 изменений, 1/2/3 варианта.

MST содержит 2 ребра этого веса

Мы можем заменить одно из них на оставшееся, если это возможно. 0/1 изменений, 1/2/3 варианта.

MST содержит 3 ребра этого веса

Мы не можем менять рёбра, потому что все три уже взяты. 0 изменений, 1 вариант.

Но как нам найти количество вариантов для каждого веса? Что ж, давайте подвесим наше MST за любую вершину, затем запустим DFS из корня и запишем времена входа и выхода для каждого ребра (tin & tout для рёбер).

Теперь, например, мы хотим проверить, может ли ребро $$$e_1$$$ (из MST) быть заменено ребром $$$e_2$$$ (не из MST). Пусть $$$v$$$ и $$$u$$$ — концы ребра $$$e_2$$$, а также пусть $$$e_v$$$ — ребро из родителя $$$v$$$ в $$$v$$$ (аналогично для $$$e_u$$$). Тогда ребро $$$e_1$$$ может быть заменено ребром $$$e_2$$$, если $$$e_1$$$ является предком только одного из рёбер $$$e_v$$$ или $$$e_u$$$ (мы можем проверить, что одно ребро является предком другого точно также, как мы обычно делаем это для вершин, используя времена входа и выхода, которые мы подсчитали для каждого ребра). Вы можете нарисовать несколько картинок, чтобы понять, почему это так (этот метод также прекрасно работает для рёбер $$$e_v$$$ и $$$e_u$$$, расположенных на одном вертикальном пути в дереве). Вам даже не нужно находить LCA $$$v$$$ и $$$u$$$!

Проверяя каждую замену способом, описанным ранее, вы можете легко найти количество вариантов для каждого веса.

Последний шаг. Для того чтобы найти все варианты формирования MST, вам всего лишь нужно перемножить количество вариантов для каждого веса. Это означает, что любая теоретически возможная комбинация замен рёбер не приведёт к распаду графа!

Асимптотическая сложность: $$$O(m\log n)$$$.

Спасибо за то, что прочитали! Я надеюсь, вам понравилось!