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