Закрыть порталы

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

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

Нам требуется выбрать некоторое множество вершин, чтобы по ним можно было добраться от любого из трех изначально заданных связных множеств вершин до другого. Обозначим изначальные множества за $$$A_1$$$, $$$A_2$$$ и $$$A_3$$$, а искомое множество связывающих их вершин — за $$$B$$$. Тогда заметим, что каждая из вершин $$$B$$$ лежит на каком-то пути между $$$A_i$$$ и $$$A_j$$$ для $$$i \neq j$$$, иначе эту вершину можно удалить, и ответ станет меньше.

Посмотрим, как множество $$$B$$$ может выглядеть.

  1. Рассмотрим путь $$$p_{1,2} \subseteq B$$$ между $$$A_1$$$ и $$$A_2$$$, и аналогичные пути $$$p_{1,3}$$$ и $$$p_{2,3}$$$. Заметим, что $$$B = p_{1,2} \cup p_{1,3} \cup p_{2,3}$$$, все остальные вершины можно удалить.
  2. Пусть какие-то два из этих путей, например, $$$p_{1,2}$$$ и $$$p_{1,3}$$$, не пересекаются. Тогда заметим, что существует путь от $$$A_2$$$ до $$$A_3$$$ через $$$A_1$$$, поэтому $$$B = p_{1,2} \cup p_{1,3}$$$.
  3. Если же любые два выбранных пути пересекаются, то рассмотрим $$$v$$$ — какую-то из вершин на пересечении $$$p_{1,2}$$$ и $$$p_{1,3}$$$. Заметим, что если оставить в $$$B$$$ только $$$p_{1,2}$$$ и часть $$$p_{1,3}$$$ от $$$v$$$ до $$$A_3$$$, то также все множества будут взаимодостижимы, поэтому $$$B = \bigcup\limits_{i=1}^3 \mathtt{path}(v, A_i)$$$.

Итого, $$$B$$$ можно получить либо как объединение двух минимальных путей между двумя парами данных множеств, либо как объединение трех кратчайших путей от некоторой вершины $$$v$$$ до каждого из множеств. Чтобы все эти кратчайшие пути вычислить, сделаем множественный bfs из каждого из $$$A_i$$$ и найдем $$$\mathtt{d}_i(v)$$$ — длину кратчайшего пути от какой-то из вершины $$$A_i$$$ до $$$v$$$.

Теперь если обозначить за $$$\mathtt{D}_i(j)$$$ величину $$$\min\limits_{v \in A_j} \mathtt{d}_i(v)$$$, ответ равен $$$$$$\min\left(\mathtt{D}_1(2) + \mathtt{D}_1(2), \mathtt{D}_2(1) + \mathtt{D}_2(3), \mathtt{D}_3(1) + \mathtt{D}_3(2), \min\limits_{v=1}^n (\mathtt{d}_1(v) + \mathtt{d}_2(v) + \mathtt{d}_3(v) + 1)\right) \text{.}$$$$$$ Только надо аккуратно учесть, что расстояния надо считать в вершинах, а не в ребрах.