Изменения

В статье описывается один из сильно полиномиальных алгоритмов решения [[Поток минимальной стоимости #Задача о потоке минимальной стоимости|задачи о поиске потока минимальной стоимости]].==Алгоритм ==Приведенный алгоритм основан на идее [[Поток минимальной стоимости #Метод устранения отрицательных циклов в остаточной сети|алгоритма Клейна отмены цикла отрицательного веса]]. Выбор цикла минимального среднего веса== Приведенный вместо случайного делает алгоритм принадлежит к классу сильно полиномиальных алгоритмовполиномиальным.

 ===Описание алгоритма===Рассмотрим некоторый цикл Обозначим как <tex>c_{f}(C)</tex> остаточную пропускную способность цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>. Обозначим его стоимость Cтоимость цикла <tex>C</tex> обозначим за <tex>p(C)</tex>, а его длину (число ребер, входящих в циклнего ребер) {{---}} за <tex>\texttt{len}(C)</tex>. 

|definition='''Средним весом цикла''' называется будем называть отношение его стоимости к его длине <tex>\mu (C)=\frac{p(C)}{\texttt{len}(C)}</tex>}} ====Сам алгоритм====* '''Шаг1'''. Рассмотрим некоторый поток <tex>f</tex>. Находим * '''Шаг2'''. Найдем цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.Иначе, отменим * '''Шаг3'''. Отменим цикл <tex>C</tex>, пустив по нему максимально возможный поток: <tex>f := f + c_{f}(C)\cdot f_{C}</tex>, где <tex>c_{f}(C)</tex> {{---}} остаточная пропускная способность цикла <tex>C</tex>.Вернемся Перейдем к началу алгоритма'''шагу 1'''. ====Время работы алгоритма=Сложность===

 ===Алгоритм поиска цикла минимального среднего веса=======наивный Наивный способ====Устроим [[Вещественный двоичный поиск |двоичный поиск]].установим Установим нижнюю и верхнюю границы величины среднего веса цикла <tex>l</tex> и <tex>r</tex>соответственно, вычислим середину серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех реберсети. Если теперь в нашем графе нашей сети есть отрицательный цикл, значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда сдвигаем правую границу на <tex>m</tex>, иначе {{---}} левую.

====способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценки====