Изменения

== Суть Идея ==Пусть существует граф <tex>G</tex> и <tex>\forall (u,v)\in E\colon c_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток по этим путям, а затем по всем остальным. Пусть <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 \log_2 U \rceil = n </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\leftarrow 0</tex> <tex>\Delta\leftarrow 2^{\lfloor\log_2Ulog_2 U \rfloor}</tex> '''while''' <tex>\Delta>0</tex>