Изменения

==Решение==

<wikitex>Для решения этой задачи нам понадобится изменить исходную сеть $G$ в $G'$ следующим образом. Сначала добавим в граф вершины $x$ {{---}} новый исток и $y$ {{---}} новый сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим ребра $x \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} y$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$.

Проанализируем новую сеть. Каждое ребро изначального графа мы заменили на три новых. Тот факт, что по изначальному ребру $e_i$ должен течь поток $l_i \leqslant f_i \leqslant c_i$ означает, что в новой сети по ребру $(x, v_{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который раньше мог вытекать из $v_{from}$ по изначальному ребру, заменяется на поток, который может течь по ребрам $(v_{from}, v_{to})$ и $(v_{from}, y)$ (это ясно из того, что сумма их пропускных способностей в полученном графе равна $c_i$). То же самое верно и в вершине $v_{to}$, куда суммарный возможный входящий поток не изменился. Таким образом, ясно, что любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя ребрами в полученном графе. Заметим, что в этом самом графе все $l_i = 0$, то есть мы имеем обыкновенную сеть.