Как свести двудольное паросочетание к задаче о максимальном потоке?

Построение сети. Пусть доли $L$ и $R$.

1. Добавляем суперисток $s$ и суперсток $t$.
2. Из $s$ в каждую вершину $L$ — ребро пропускной способности 1.
3. Из каждой вершины $R$ в $t$ — ребро пропускной способности 1.
4. Каждое ребро исходного графа $l \to r$ — пропускной способности 1 (направление $L \to R$).

Максимальный поток в этой сети = размер максимального паросочетания. Рёбра $L\to R$, по которым течёт единичный поток, и образуют паросочетание. Единичные пропускные на $s\to L$ и $R\to t$ гарантируют, что каждая вершина участвует не более чем в одной паре.

// L = [0..nL), R = [nL..nL+nR), s = nL+nR, t = s+1
int S=nL+nR, T=S+1; n=T+1;
for(int l=0;l<nL;l++) add_edge(S, l, 1);
for(int r=0;r<nR;r++) add_edge(nL+r, T, 1);
for(auto&[l,r]:edges) add_edge(l, nL+r, 1);
int matching = maxflow(S, T);

Про скорость: да! На сети с единичными пропускными способностями Диниц работает за $O(E\sqrt{V})$ — это в точности оценка Хопкрофта-Карпа. Причина: число фаз ограничено $O(\sqrt{V})$ (известный результат для единичных сетей), а каждая фаза — $O(E)$. Так что «Диниц на двудольной сети» и есть Хопкрофт-Карп по сути.

Это удобно, когда у вас уже написан Диниц: не надо отдельно кодить Куна/Хопкрофта.