Изменения

Этот алгоритм работает в предположении, что все пропускные способности ребер целые. Пусть <tex>U</tex> - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи (для каждого ребра отведем <tex>n+1:=\lfloor\log U\rfloor+1</tex>). Занумеруем биты с младшего (0-ой) по старший (n-ный). Тогда

<tex>\forall (u,v)\in E:c(u,v)=2^na_nn*a_n(u,v)+...+2a_12*a_1(u,v)+a_0(u,v); a_i(u,v)\in\{0,1\}</tex>

Будем решать задачу методом Форда-Фалкерсона сначала для графа с урезанными пропускными способностями <tex>c_0(u,v):=a_n(u,v)</tex>. Решив ее и получив поток <tex>f_0</tex>, добавим следующий бит и вычтем грубое приближение. То есть <tex>\forall (u,v)\in E:c_1(u,v):=2a_n2*a_n(u,v)+a_{n-1}(u,v)-2f_02*f_0(u,v)</tex>. Далее наше приближение становится точнее и точнее, пока не станет решением для исходной задачи.