Изменения

|definition=Дано число <mathtex>f_0</mathtex> и транспортная сеть <mathtex>\,G(V,E)</mathtex> с источником <mathtex>s \in V</mathtex> и стоком <mathtex>t \in V</mathtex>, где ребра <mathtex>(u,v) \in E</mathtex> имеют пропускную способность <mathtex>\,c(u,v)</mathtex>, поток <mathtex>\,f(u,v)</mathtex> и цену <mathtex>\,p(u,v)</mathtex>.

:<mathtex>\sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </mathtex>.:<mathtex>\sum_{u,v \in V} f(u,v) = f_0</mathtex>

*Найти любой поток величины <mathtex>f_0</mathtex>, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток.