Изменения

* '''Шаг 1'''. Требуется найти максимальный поток минимальной стоимостиОпределим для каждого прямого ребра <tex>(u,v)</tex> обратное ребро <tex>(v,u)</tex>. Определим его характеристики: <tex>c(v,u)=0</tex>, <tex>f(v,u)=-f(u,v)</tex>, <tex>a(v,u)=-a(u,v)</tex>.

* '''Шаг 3'''. Построим Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть , где каждому ребру будет соответствовать величина <tex>G_fa(u,v) \cdot (c(u,v) - f(u,v))</tex>. Таким образом обратные ребра в остаточной сети будут иметь неположительную стоимость.* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательные циклы отрицательный цикл в остаточной построенной сети. Если нет отрицательный цикл не нашелся {{---}} перейдем к '''шагу 76'''.* '''Шаг 5'''. Выберем один из отрицательных циклов.* '''Шаг 6'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к '''шагу 54'''.* '''Шаг 76'''. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости найден.