То, что ту задачу никто не решил на контесте - можно сказать, недоразумение. Обе команды застряли на других задачах (в том числе даже, возможно, более сложных задачах, чем эта).
Алгоритм: мы перебираем удаляемую вершину. Удаляем эту вершину из графа. Теперь в нём надо найти глобальный мин. разрез (т.е. минимальный среди минимальных разрезов по всем возможным истокам и стокам). Можно перебрать исток и сток, и уже запускать поток (кстати, лучше даже не за куб, а Форда-Факлерсона, почему - скажу ниже). Вот, но это долго - весь алгоритм получается за N^3 * время_потока.
Но заметим, что все пары истоков и стоков перебирать не обязательно, а достаточно зафиксировать произвольный исток, и перебирать только сток. Действительно, зафиксируем любой исток s. В оптимальном ответе (мин. разрезе) он будет находиться в одной доле, а тогда, чтобы найти этот мин. разрез, нам достаточно "угадать" с выбором t так, чтобы он попал в другую долю. Таким образом, для нахождения глобального мин. разреза достаточно зафиксировать, скажем, s=1, и перебирать t=2..n. В итоге получается N^2 * время_потока.
На первый взгляд, это кажется много. Действительно, берём какой-нибудь достаточно хитроумный поток за куб (проталкиванием), и алгоритм получается с асимптотикой N^5. Вот, но утверждается, что как ни странно, можно вместо хитрого потока брать обычного Форда-Фалкерсона. Например, из соображений, что величина потока не может быть большой. И то это будет сильная оценка сверху. Опять же, граф не совсем плотный, и сделать тест, на котором Форд-Фалкерсон будет выполнять много итераций при всех возможных deleted_vertex и t, невозможно. В итоге моё решение за 300 мс работает.
Да, и собственно по мотивам этой задачи я сел разбираться с алгоритмом Штор-Вагнера для нахождения глобального мин. разреза за O(N^3). Решение, основанное на этом алгоритме, имеет общую асимптотику O(N^4), и проходит за 0.