1632
правки
Изменения
м
rollbackEdits.php mass rollback
* '''Шаг 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>.
* '''Шаг 2'''. Для каждого ребра зададим поток равный <tex>0</tex>.
* '''Шаг 3'''. Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть, где каждому ребру будет соответствовать величина <tex>a(u,v) \cdot (c(u,v) - f(u,v))</tex>. Таким образом обратные ребра в остаточной сети будут иметь неположительную стоимость.* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательный цикл в построенной сети(отрицательный цикл ищется по стоимости ребра, т.е. ребра имеют вес <tex>a(u,v)</tex>). Если отрицательный цикл не нашелся {{---}} перейдем к '''шагу 6'''.
* '''Шаг 5'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к '''шагу 4'''.
* '''Шаг 6'''. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости найден.
===Метод дополнения потока вдоль путей минимальной стоимости===
{{main|Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимостиПоиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости}}
===Использование потенциалов Джонсона===
{{main|Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимостиИспользование потенциалов Джонсона при поиске потока минимальной стоимости}}
== См. также ==
