276
правок
Изменения
→Описание
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}
===Описание===
Обозначим как <tex>c_{f}(C)</tex> остаточную [[Определение сети, потока|пропускную способность ]] цикла <tex>C</tex> при протекании в сети потока <tex>f</tex>.
Cтоимость цикла <tex>C</tex> обозначим за <tex>p(C)</tex>, а длину (число входящих в него ребер) {{---}} за <tex>\texttt{len}(C)</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>. Перейдем к '''шагу 1'''.
===Сложность===
<tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом
