Какая реальная асимптотика Диница на двудольном паросочетании и на сетях с единичными пропускными?

Общая оценка Диница — $O(V^2 E)$ — пессимистична. На специальных сетях она резко улучшается из-за ограничения на число фаз.

1. Единичные пропускные на двудольном паросочетании / сети с единичными capacity: $O(E\sqrt{V})$. Ключ — лемма: после $\sqrt{V}$ фаз остаточный поток (сколько ещё осталось добрать) не превышает $\sqrt{V}$, а каждая оставшаяся единица потока требует не больше одной фазы. Значит фаз всего $O(\sqrt{V})$, каждая $O(E)$ → $O(E\sqrt{V})$. Это в точности оценка Хопкрофта-Карпа для паросочетания.

2. Единичные сети (unit-capacity networks), где у каждой внутренней вершины степень вход/выход = 1: $O(E\sqrt{E})$ или $O(E\sqrt{V})$. Аналогичный аргумент: длина кратчайшего пути растёт, и после $O(\sqrt{E})$ фаз поток почти добран.

3. Планарные сети, сети с малыми целыми capacity — свои улучшенные оценки.

Практический вывод: если в задаче все пропускные = 1 (паросочетания, Менгер, выбор непересекающихся путей), смело считайте Диница как $O(E\sqrt{V})$ — он пройдёт там, где «общий» max-flow по верхней оценке кажется медленным. Память всегда $O(V+E)$.

На произвольных больших пропускных же оценка остаётся $O(V^2E)$, но на практике Диниц почти всегда работает кардинально быстрее теоретической границы — поэтому он де-факто стандарт в CP.