Изменения

Перейти к: навигация, поиск

Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости

46 байт убрано, 15:32, 24 января 2016
→‎Реализация
<tex>flow[edge] = 0</tex>
'''while''' <tex>\exists</tex> путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>:
<tex>path = </tex> путь <tex>s \leadsto t</tex> с наименьшей стоимостью <tex>P</tex> maxFlow = <tex>maxFlow = \displaystyle \min_{edge \in path} C[edge] - flow[edge]</tex>
'''for''' <tex>edge</tex> '''in''' :
<tex>flow[edge] = flow[edge] + maxFlow </tex> '''return''' <tex>flow</tex>
===Асимптотика===
Mr ivan777
147
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/51834»

Навигация