Почему наивный Форд-Фалкерсон с DFS может работать очень долго или не завершиться?
Написал Форд-Фалкерсон: ищу любой увеличивающий путь обычным DFS и пускаю поток. На одном тесте программа работает подозрительно долго, хотя граф маленький (всего 4 вершины, но большие пропускные). Почему так и как это лечить?
2 ответа
Проблема в том, что наивный 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 алгоритм теоретически даже не завершается.
Лечение (любое из):
- Эдмондс-Карп — брать кратчайший путь через BFS. $O(VE^2)$, не зависит от величины потока.
- Диниц — слоистая сеть + блокирующий поток. $O(V^2E)$, на практике быстрее всех.
- Capacity scaling — пускать сначала по толстым рёбрам. $O(E^2\log U)$.
На олимпиаде по умолчанию пишите Диница — он обходит эту патологию и быстр на реальных тестах.
Добавлю про коварность: на случайных или «дружелюбных» тестах наивный FF с DFS часто проходит, потому что плохих путей не возникает. Поэтому баг легко не заметить локально, а на максимальном/специально подобранном тесте словить TLE. Никогда не сдавайте наивный FF в задачах, где пропускные могут быть большими (> нескольких тысяч). Если граф с единичными пропускными (паросочетания, Менгер) — наивный FF фактически вырождается в Куна и работает $O(VE)$, там это допустимо. Но привычку лучше выработать сразу: max-flow = Диниц.