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) \times 2^n, a_i(u, v) \in \{0, 1\} </tex>
Методом Форда-Фалкерсона находим поток <tex> f_0 </tex> для графа с урезанными пропускными способностями <tex> c_0(u, v) = a_n(u, v) </tex>.
