Здавствуйте! Все знают, что |MinCut| = |MaxFlow| в сети. Кто знаком с темой может прокрутить вниз, там вопрос.

[newbie mode] Как найти какие именно ребра являются разрезом? Тут вроде тоже все понятно, разделим множество вершин на два множества: S — множество достижимых вершин из истока по ненасыщенным ребрам и T = V / S. Ребра, которые соединяют вершины из разных множеств и будут одним из ответов.

Как найти вершинный разрез? Учили так: разделим каждую вершину v на 2 вершины: v₁ для входящих и v₂ для выходящих. Сделаем так же ребро v₁ -  > v₂ с пропускной способностью 1. Далее найдем макс.поток и размер потока будет равен минимальному вершинному разрезу. Но как теперь найти ответ?

В задаче на USACO trainings (telecow, 5.4.5) проходит такое решение для |V| ≤ 100, |E| ≤ 600:

Будем по очереди удалять ребро между v₁ и v₂ для каждой вершины и будем заного находить поток. Если поток уменьшился на единицу, то эта вершина входит в раздрез.

Мне не очень понравилось это решение, ведь делая это алгоритмом Диници, это будет работать не мало: O((|V||E|)²), где кол-во вершин увеличивается в 2 раза, а кол-во ребер примерно в 4 раза(обратные ребра и по 2 ребра на каждое, так как ребра не ориентированны), получается где-то 100 * 2 * 600 * 4 в квадрате итераций? Сначала я испугался такой цифры, но вспомнив, что ребра с пропускной способностью в единицу делают ее еще быстрее, то выходит помножиное на |V| вызовов, то выходит около 6 * 10⁶, что приемлемо. [/newbie mode]

Но как находить вершинный разрез, когда вершин и ребер еще больше? Есть ли более оптимальное решение?