Стабилизация мультивселенной

Автор задачи и разработчик: Даниил Орешников

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

Для начала упростим условие: дан ориентированный граф на $$$n$$$ вершинах, в которой из каждой вершины выходит ровно два ребра, и в каждую вершину входит ровно два ребра, то есть $$$\mathtt{deg}_\mathrm{in}(v) = \mathtt{deg}_\mathrm{out}(v) = 2$$$ для всех $$$v$$$. Требуется выбрать несколько циклов, покрывающих все вершины по одому разу, при чем чтобы интервалы чисел на выбранных ребрах имели общее непустое пересечение.

Сразу будем описывать сведение задачи к 2-SAT, то есть к решению логической формулы в 2-КНФ, в которой несколько клозов (скобок, состоящих из логического «ИЛИ» двух переменных или их отрицаний) перечислены через логическое «И». Для этого поймем, как описать в терминах 2-SAT условия задачи. Вместо «ИЛИ» будем использовать следствия (импликации), так как их можно взаимно выразить друг из друга, а решение задачи 2-SAT строится как раз на импликациях.

  1. Заведем по переменной на каждое ребро графа. Переменная $$$e_i$$$ будет означать, выбрано ли $$$i$$$-е ребро. Тогда:
    • Из каждой вершины должно выходить только одно выбранное ребро, то есть $$$e_{2i+1} \to \lnot e_{2i+2}$$$ и, наоборот, $$$e_{2i+2} \to \lnot e_{2i}$$$.
    • Аналогично, в каждую вершину должно входить ровно одно выбранное ребро, то есть если в вершину $$$v$$$ входят ребра $$$i$$$ и $$$j$$$, надо добавить условия $$$e_i \to \lnot e_j$$$ и $$$e_j \to \lnot e_i$$$.

  2. Заведем также по переменной $$$m_c$$$ на выражения вида «выбранная мощность $$$m$$$ не превосходит $$$c$$$». Они связываются следующей логикой:
    • Из того, что $$$m \leqslant c$$$, следует, что $$$m \leqslant c + 1$$$, поэтому надо добавить следствие $$$m_c \to m_{c+1}$$$ для всех $$$c$$$ от $$$0$$$ до $$$10^5$$$.
    • Из того, что мы выбрали ребро $$$i$$$, следует, что $$$m \in [a_i, b_i]$$$, то есть $$$\leqslant b_i$$$ и $$$\not\leqslant a_i - 1$$$. Добавляем следствия $$$e_i \to m_{b_i}$$$ и $$$e_i \to \lnot m_{a_i - 1}$$$.

Заметим, что построенная формула полностью описывает все условия из задачи. И любое решение этой формулы однозначно транслируется в корректный ответ для нашей задачи. Только надо не забывать, что когда мы добавляем следствие $$$a \to b$$$, надо также добавить и равнозначное ему $$$\lnot b \to \lnot a$$$.

Теперь, для решения этой формулы, применим стандартный алгоритм решения 2-SAT, основанный на выделении компонет сильной связности. Если мы получили противоречие, то решения нет, а иначе — выбираем те $$$e_i$$$, которые истинны, и получаем список выбранных ребер, а также выбираем максимальное $$$c$$$, при котором $$$m_c$$$ истинно, и получаем значение $$$m$$$. Суммарное время работы алгоритма равно $$$\mathcal{O}(n + m_{\max})$$$.