Почему наивный Форд-Фалкерсон с DFS может работать очень долго или не завершиться?

Проблема в том, что наивный DFS может выбирать плохие увеличивающие пути, пуская по 1 единице за раз, хотя пропускные огромные.

Классический «злой» тест. Граф: $s, a, b, t$. Рёбра:

s->a : 10^9
s->b : 10^9
a->b : 1        (узкая «диагональ»)
a->t : 10^9
b->t : 10^9

Если DFS каждый раз ходит через диагональ $a\to b$ (то туда, то обратно по обратному ребру), он пускает по 1 единице за итерацию и делает порядка $2\cdot 10^9$ итераций. Каждая итерация — $O(E)$, итого катастрофа, хотя ответ ($2\cdot 10^9$) находится за 2 «умных» пути.

Асимптотика наивного FF: $O(E \cdot \text{flow})$ — зависит от величины потока, а не только от размера графа. При больших пропускных flow огромен → TLE. На иррациональных capacity алгоритм теоретически даже не завершается.

Лечение (любое из):

1. Эдмондс-Карп — брать кратчайший путь через BFS. $O(VE^2)$, не зависит от величины потока.
2. Диниц — слоистая сеть + блокирующий поток. $O(V^2E)$, на практике быстрее всех.
3. Capacity scaling — пускать сначала по толстым рёбрам. $O(E^2\log U)$.

На олимпиаде по умолчанию пишите Диница — он обходит эту патологию и быстр на реальных тестах.