272
правки
Изменения
Нет описания правки
== Идея ==
Суть алгоритма в нахождении сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток по этим путям, а затем по всем остальным. Пусть <tex>U</tex> - максимальная пропускная способность. Введём параметр <tex>\Delta = 2^{\lfloor\log_2U\rfloor}</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше, чем <tex>\Delta</tex>, и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым значением параметра. При значении <tex>\Delta</tex>, равном единице, данный алгоритм становится идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса — Карпа]]. Из этого следует, что алгоритм корректен.
Пусть <tex> G </tex> — граф, <tex> \forall(u, v) \in EG \colon c(u,v) \in \mathbb{Z_+}, U = \max\limits_{(u, v) \in EG} c(u, v) </tex> — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать <tex> \lceil lfloor \log_2 U \rceil rfloor + 1 = n + 1 </tex> бит.
<tex> c(u, v) = \sum\limits_{i = 0}^{n - 1} a_i(u, v) 2^n, a_i(u, v) \in {0, 1} </tex> Методом Форда-Фалкерсона найдем поток <tex> f_0 </tex> для графа с урезанными пропускными способностями <tex> c_0(u, v) = a_n(u, v) </tex>.Добавим следующий бит и находим следующее приближение После <tex> n + 1 </tex> итерации получим ответ к задаче
== Оценка сложности ==
{{Утверждение
|statement=
Время работы алгоритма — <tex> O(E^2 \log U) </tex>.
|proof=
[[Файл:Scaling.jpg|right]]
На каждом шаге алгоритм выполняет в худшем случае <tex>O(E)</tex> увеличений потока. Докажем это. Пусть <tex>\Delta = 2^k</tex>. В конце шага множество вершин графа можно разбить на две части: <tex>A_k</tex> и <tex>\overline{A_k}</tex>. Все рёбра, выходящие из <tex>A_k</tex>, имеют остаточную пропускную способность менее <tex>2^k</tex>. Наибольшее количество рёбер между <tex>A_k</tex> и <tex>\overline{A_k}</tex> равно <tex>E</tex>. Следовательно, остаточный поток (поток, который может быть получен на оставшихся шагах) на фазе с текущим значением <tex>k</tex> максимально составляет <tex>2^kE</tex>. Каждый увеличивающий путь при данном <tex>k</tex> имеет пропускную способность как минимум <tex>2^k</tex>. На предыдущем шаге, с масштабом <tex>k+1</tex>, остаточный поток ограничен <tex>2^{k+1}E</tex>. Значит максимальное число появившихся увеличивающих путей равно <tex>2E</tex>. Увеличивающий путь можно найти за <tex>O(E)</tex>, используя [[Обход_в_ширину | BFS]]. Количество шагов <tex>O(\log_2U)</tex>. Итоговая сложность <tex>O(E^2\log_2U)</tex>.
}}
== Псевдокод ==
