272
правки
Изменения
→Идея
Идея алгоритма в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по ним, а затем по всем остальным.
Пусть дан граф <tex> G </tex> — граф, с целыми пропускными способностями: <tex> \forall(u, v) \in EG \colon c(u,v) \in \mathbb{Z_+}, </tex>.<tex> U = \max\limits_{(u, v) \in EG} c(u, v) </tex> — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать <tex> \lfloor \log_2 U \rfloor + 1 = n + 1 </tex> бит.
<tex> c(u, v) = \sum\limits_{i = 0}^n a_i(u, v) \times 2^n, a_i(u, v) \in \{0, 1\} </tex>
Добавим следующий бит и находим следующее приближение для графа с новыми пропускными способностями <tex> c_1(u, v) = 2 a_n(u, v) + a_{n - 1}(u, v) - 2 f_0(u, v) </tex>.
После <tex> n + 1 </tex> итерации получим ответ к задаче, так как после с каждым шагом приближение становится точнее.
== Оценка сложности ==
