1

Тема: SGU 402. Terrorists in Berland

В Southern Subregion 2008 была задача K, которую, в числе прочих, никто во время контеста не решил: http://acm.sgu.ru/problem.php?contest=0&problem=402.

Задача заключается в следующем - найти минимальное по стоимости множество ребер, которые достаточно удалить, чтобы в графе нашлась вершина, после удаления которой граф распадётся на компоненты связности.

Ограничения позволяют провести алгоритм за О(V^4), что вкупе с тем, что задача напоминает задачу о минимальном разрезе, приводит к следующей схеме решения:
Пробуем удалить каждую вершину, некоторым образом преобразовываем граф, и пускаем макспоток за О(V^3).

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

Буду рад любой помощи по этому вопросу.

2 Отредактировано e-maxx (2009-08-16 14:59:27)

Re: SGU 402. Terrorists in Berland

То, что ту задачу никто не решил на контесте - можно сказать, недоразумение. Обе команды застряли на других задачах (в том числе даже, возможно, более сложных задачах, чем эта).

Алгоритм: мы перебираем удаляемую вершину. Удаляем эту вершину из графа. Теперь в нём надо найти глобальный мин. разрез (т.е. минимальный среди минимальных разрезов по всем возможным истокам и стокам). Можно перебрать исток и сток, и уже запускать поток (кстати, лучше даже не за куб, а Форда-Факлерсона, почему - скажу ниже). Вот, но это долго - весь алгоритм получается за N^3 * время_потока.

Но заметим, что все пары истоков и стоков перебирать не обязательно, а достаточно зафиксировать произвольный исток, и перебирать только сток. Действительно, зафиксируем любой исток s. В оптимальном ответе (мин. разрезе) он будет находиться в одной доле, а тогда, чтобы найти этот мин. разрез, нам достаточно "угадать" с выбором t так, чтобы он попал в другую долю. Таким образом, для нахождения глобального мин. разреза достаточно зафиксировать, скажем, s=1, и перебирать t=2..n. В итоге получается N^2 * время_потока.

На первый взгляд, это кажется много. Действительно, берём какой-нибудь достаточно хитроумный поток за куб (проталкиванием), и алгоритм получается с асимптотикой N^5. Вот, но утверждается, что как ни странно, можно вместо хитрого потока брать обычного Форда-Фалкерсона. Например, из соображений, что величина потока не может быть большой. И то это будет сильная оценка сверху. Опять же, граф не совсем плотный, и сделать тест, на котором Форд-Фалкерсон будет выполнять много итераций при всех возможных deleted_vertex и t, невозможно. В итоге моё решение за 300 мс работает.

Да, и собственно по мотивам этой задачи я сел разбираться с алгоритмом Штор-Вагнера для нахождения глобального мин. разреза за O(N^3). Решение, основанное на этом алгоритме, имеет общую асимптотику O(N^4), и проходит за 0.

3

Re: SGU 402. Terrorists in Berland

Спасибо. Очень познавательный ответ.