Довольно часто попадаются задачи на нахождение максимального потока / минимального сечения. В этом случае используют алгоритмы Форда-Фалкерсона или Эдмондса-Карпа, иногда к этому прибавляется масштабирование, что ощутимо ускоряет дело. Самой сложной частью в такой задаче считается ее сведение к вычислению потока.

Но совсем недавно я наткнулся на задачу в архиве spoj'а FASTFLOW в которой требуется вычислить в очень маленькое время максимальный поток при больших входных данных. После написания решения на Java и получения TLE я переписал его на C++, но опять алгоритм Эдмондса-Карпа с масштабированием оказался бессилен. Никаких других методов я нигде не нашел, поэтому обращаюсь за помощью. Думаю этот вопрос будет интересен не только мне, так как обычно его не освещают слишком глубоко.

Заранее благодарен.