Как восстановить сам минимальный разрез после вычисления максимального потока?

После того как maxflow завершился, в остаточной сети уже нет пути $s\to t$. Делаем простой обход:

1. Запускаем BFS/DFS из $s$ только по рёбрам с положительной остаточной пропускной ($cap > 0$).
2. Множество достижимых вершин — это $S$. Остальные — $T$ (туда точно попадёт $t$).
3. Рёбра минимального разреза — это исходные рёбра $(u,v)$ такие, что $u \in S$, $v \in T$ (по ним в остаточной сети течь нельзя — они насыщены).

vector<char> vis;
void reach(int v){
    vis[v]=1;
    for(int id:g[v]) if(e[id].cap>0 && !vis[e[id].to]) reach(e[id].to);
}
// после maxflow(s,t):
vis.assign(n,0); reach(s);
// S = {v : vis[v]}, рёбра разреза:
for(int v=0; v<n; v++) if(vis[v])
    for(int id:g[v]) if(!(id&1)) { // только прямые рёбра исходного графа
        int to=e[id].to;
        if(!vis[to]) {
            // (v, to) — ребро минимального разреза
        }
    }

Важно: разрез образуют только исходные (прямые) рёбра, идущие из $S$ в $T$. Чтобы их отличать, либо помечайте флагом «настоящее ли это ребро», либо (как выше) опирайтесь на чётность индекса, если все исходные рёбра добавлялись через add_edge первыми в паре. Сумма их пропускных способностей обязана равняться значению потока — это хорошая проверка корректности.