272
правки
Изменения
→Идея
== Идея ==
Пусть <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> \lfloor \log_2 U \rfloor + 1 = n + 1 </tex> бит.
<tex> c(u, v) = \sum\limits_{i = 0}^n 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> c_1(u, v) = 2 a_n(u, v) + a_{n - 1}(u, v) - 2 f_0(u, v) </tex>.
После <tex> n + 1 </tex> итерации получим ответ к задаче, так как после с каждым шагом приближение становится точнее.
== Оценка сложности ==
