Задача о нахождении максимального потока в графе звучит следующим образом: Имеется исток,сток и соединяющие их трубы, имеющие некоторую пропускную способность. Требуется выяснить, сколько нужно по каждой трубе пропускать воды, чтобы со стока доходило максимальное колличество воды. Алгоритм выглядит следующим образом:
1. Найти увеличивающий путь от истока к стоку(некоторая последовательность труб, ведущая от истока к стоку, причем сдесь не должно быть ни одной полностью заполненной трубы)
2. Увеличить колличество воды, текущее по каждой трубе этого пути на минимум из колличества воды, которую можно пропустить по каждой из труб
3. Повторять, пока находится такой путь
Особое внимание следует обращать на т.н. обращение потока: Если по трубе с пропускной способностью 10 течет в одном направлении 7 воды, то в обратном можно пропустить 17!
Сложность алгоритма O(N^3), если для поиска пути использовать очередь.