Временная сложность метода Форда-Фалкерсона в потоковой сети с ребрами единичной пропускной способности

O(M*f) — известная оценка времени работы Форда-Фалкерсона на графах с целочисленными пропускными способностями, где M — количество ребер, а f — значение максимального потока, просто потому, что легко найти возрастающие пути в O(M) каждый, и каждый такой путь увеличивает поток не менее чем на 1.

Если в вашем графе нет повторяющихся ребер (то есть нет пары ребер с одинаковыми начальной и конечной вершинами) и каждое ребро имеет единичную пропускную способность, то максимальный поток f не превышает количество вершин N ( только потому, что от источника исходит не более N-1 ребер), и, следовательно, сложность действительно O(N*M).

Однако, если в вашем графе разрешено иметь повторяющиеся ребра (но все же каждое ребро имеет емкость 1), то f может быть больше, чем N, и вплоть до M, а временная сложность может стать O(M*M), и это нетрудно сделать. с примером, где такая сложность имеет место.