276
правок
Изменения
→Наивный способ
===Наивный способ===
Устроим [[Вещественный двоичный поиск |двоичный поиск]].
Установим нижнюю и верхнюю границы величины среднего веса цикла <tex>l</tex> и <tex>r</tex> соответственно, вычислим серединное значение <tex>m</tex> и отнимем полученную величину <tex>m</tex> от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл(этот факт можно проверить при помощи [[Алгоритм Форда-Беллмана #Нахождение отрицательного цикла|алгоритма Форда-Беллмана]]), значит существует цикл с меньшим средним весом, чем <tex>m</tex>. Тогда сдвигаем правую границу на продолжим поиск среди значений в диапазоне от <tex>l</tex> до <tex>m</tex>, иначе {{---}} левуюот <tex>m</tex> до <tex>r</tex>.
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла.
===способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценки===
