Я реализовал первую фазу алгоритма максимальной метки push-метки для максимального потока, но я не мог найти никаких ресурсов о том, как реализовать вторую фазу, т.е. конвертировать прессовую сеть в действительную сеть потока.Как преобразовать прессовую сеть с избыточным потоком в поточную сеть
Если вам действительно нужен максимальный поток (можно получить минимальный разрез непосредственно из пре-потока и использовать его для проверки превенции), то я знаю два подхода.
Первый подход описан в оригинальной газете Голдберга - Тарьяна по алгоритму push-метки. По сути, вторая фаза реализована почти так же, как первая. Единственное различие заключается в том, что источник держится на расстоянии n (вместо раковины, на расстоянии 0). Это приводит к перенаправлению избытков обратно к источнику.
Я не уверен, где описан второй подход. Я знаю, что это в реализации Голдберга, на которой основан Boost Graph implementation (см. convert_preflow_to_flow). Концептуально, есть три шага.
До тех пор, пока предварительная подача ациклическая, отменить цикл потока, посылая достаточно потока на обратном цикле, чтобы удалить одну из дуг из графа потока.
Топологически сортировать узлы потокового графа от потолка до самого верхнего.
Для каждого узла в топологическом порядке устраните его избыток, уменьшив поток на входящих дугах (что приводит к соответствующему увеличению избытка узлов, которые еще предстоит обработать).
Практически говоря, шаги 1 и 2 предполагают поиск в глубину. Наивно, можно было бы возобновить поиск по глубине для обнаружения цикла после того, как каждый цикл будет обнаружен и отменен, но можно перемотать поиск по глубине только до той точки, где она сначала использовала дугу, которая отменяла удаление, сохраняя время до вернитесь к этому пункту поиска. Топологический порядок может быть получен как побочный продукт поиска, сохраняя отдельный обход для этапа 2.