272
правки
Изменения
Нет описания правки
== Алгоритм ==
Пусть дана [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|сеть]] <tex> G </tex>, все ребра которой имеют целочисленную пропускную способность. Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in E} c(u, v), \Delta = 2^{\lfloor\log_2U\rfloor} </tex>. Обозначим количество вершин за <tex> n </tex>, а количество ребер за <tex> m </tex>.
Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по ним, а затем по всем остальным.
1
|statement=
Максимальный поток в сети <tex> G </tex> ограничен сверху значением <tex> |f_k| + 2^k m E </tex>, где <tex> |f_k| </tex> - значение потока
|proof=
2
|statement=
Количество увеличивающих путей на <tex> k </tex>-ом уровне не превосходит <tex> 2m 2E </tex>
|proof=
Следует из предыдущей леммы. Каждый увеличивающий путь на <tex> k </tex>-ом уровне имеет пропускную способность не меньше <tex> 2^k </tex>.
3
|statement=
Количество увеличивающих путей не превышает <tex> O(m E logU) </tex>.
|proof=
Следует из предыдущей леммы и факта, что количество уровней {{---}} <tex> log_2U </tex>.
== Псевдокод ==
'''Max_Flow_By_Scaling(G,s,t)'''
<tex>f \leftarrow 0</tex> <tex>\Delta \leftarrow 2^{\lfloor\log_2U\rfloor}</tex> '''while''' <tex>\Delta \geq 1</tex> '''do while''' в <tex>G_f</tex> существует увеличивающий путь <tex>s-tp </tex> с пропускной способностью не меньшей <tex>\Delta</tex> '''do''' <tex>P\leftarrow</tex> путь с пропускной способностью не меньшей <tex>\Delta</tex> <tex>\delta \leftarrow \min\{c_{ij}c(u, v) \colon(iu,jv)\in Pp\}</tex> увеличить поток по рёбрам <tex>Pp </tex> на <tex>\delta</tex> обновить <tex>G_f</tex> <tex>f \leftarrow f + \delta</tex> <tex>\Delta \leftarrow \Delta / 2</tex> '''return''' <tex>f</tex>
== Литература ==
