Изменения
Нет описания правки
====Сам алгоритм====
Рассмотрим некоторый поток <tex>f</tex>. Находим цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
Иначе, отменим цикл <tex>C</tex>: <tex>f := f + c_{f}(C)\cdot f_{C}</tex>, где <tex>c_{f}(C) </tex> {{---}} остаточная пропускная способность цикла <tex>C</tex>.
Вернемся к началу алгоритма.
====Время работы алгоритма====
<tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом<tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
===Алгоритм поиска цикла минимального среднего веса===
====наивный способ====
Устроим двоичный поиск.
установим нижнюю и верхнюю границы <tex>l</tex> и <tex>r</tex>, вычислим середину <tex>m</tex> и отнимем величину <tex>m</tex> от всех ребер. Если теперь в нашем графе есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда сдвигаем правую границу на <tex>m</tex>, иначе {{---}} левую.
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла.
====способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценки====
