Предположим, что максимальный поток для G был рассчитан с использованием Форда-Фалкерсона, но теперь из E удалено ребро, как можно эффективно обновить максимальный поток.
Эффективно рассчитать максимальный поток с помощью Форда Фулкерсона после удаления края из потока.
Ответы (1)
Если ребро e, которое вы удалили, пересекает разрез, то максимальный поток равен |f| − c(e), где |f| — это ранее вычисленный максимальный поток, а c(e) — пропускная способность удаленного ребра.
Подробное объяснение можно найти здесь.
person
Honza Dejdar
schedule
08.12.2016
