Потоки

Задача. Есть дом, вода из которого стекает в реку по водопроводу. Водопровод — это набор однонаправленных труб, концы которых соединены с домом, рекой или одним из $n$ соединительных узлов. Также для каждой трубы известна ее прочность — сколько воды она может выдержать. Необходимо найти максимальный объем воды, который может вытекать из дома в единицу времени.

Поставим задачу более формально. Есть граф в котором выделены две вершины, соответствующие дому $s$ и реке $t$, а остальные вершины соответствуют узлам. Ребра этого графа соответствуют трубам водопровода, и у каждого ребра есть пропускная способность — максимальное количество воды, которое может по нему течь. Обозначим за $c(v, u)$ пропускную способность ребра из $v$ в $u$, а $f(v, u)$ — количество воды, текущее по нему.

Заметим некоторые свойства воды, текущей в водопроводе. Например, для любой вершины, которая соответствует узлу, объем втекающей в неё воды равен объему вытекающей из неё воды:

Это значит, что вода не может появится из ниоткуда и исчезнуть в никуда.

Также удобно считать, что у любого ребра есть ровно одно обратное, и $f(v, u) = -f(u, v)$, то есть если по ребру из $v$ в $u$ перетекает $x$ потока, то по ребру из $u$ в $v$ перетекает $-x$ потока.

Теперь замечание о втекающем и вытекающем объеме звучит так, что для любой вершины $v$, кроме истока $s$ и стока $t$: