увеличение максимального потока

[megabug]

Привет.

Есть сеть N и максимальный в ней поток Fm. Нужно увеличить этот максимальный поток. Я думаю, что самое логично - находить ребро, увеличение пропускной способности которого приводит к увеличению максимального потока. Но никак не могу сообразить как это ребро находить.

[Maslov]

Может оказаться, что одним ребром не обойтись.

Самый простой способ -- найдите любой простой маршрут из истока в сток и увеличьте пропускную способность всех ребер на нужное Вам значение $\Delta F$.

Или постройте методом Форда-Фалкерсона остаточную сеть, затем возьмите в ней любой маршрут из истока в сток и увеличьте остаточную пропускную способность составляющих его ребер до величины $\Delta F$.