272
правки
Изменения
→Идея
<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> f_0 </tex> для графа <tex> G_0 </tex> с урезанными пропускными способностями <tex> c_0(u, v) = a_n(u, v) </tex>.Добавим следующий бит и находим следующее приближение для графа <tex> G_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> итерации получим ответ к задаче.
