Как восстановить сами рёбра паросочетания и пути потока после запуска max-flow?

Паросочетание. Если строили сеть из двудольного графа (рёбра $l\to r$ пропускной 1), то пара существует там, где по прямому ребру $l\to r$ прошёл поток, то есть его остаточная пропускная стала 0, а у обратного — 1.

// для каждого прямого ребра l->r (исходного графа):
for(int l=0; l<nL; l++)
    for(int id : g[l]) {
        int to = e[id].to;
        if(to >= nL && to < nL+nR) {        // это ребро в правую долю
            if(e[id].cap == 0)              // поток прошёл => пара
                cout << l << " matched with " << to-nL << "\n";
        }
    }

Признак «поток прошёл» = e[id].cap == 0 для ребра, изначально имевшего cap=1. Эквивалентно: e[id^1].cap == 1 (на обратном появился остаток).

Пути потока (декомпозиция потока). Любой поток раскладывается на пути $s\to t$ (и циклы, которые можно отбросить). Жадно:

// f[id] = пущенный поток по ребру = orig_cap[id] - e[id].cap (для прямых рёбер)
vector<int> path;
while(/* есть исходящий поток из s */){
    path.clear(); int v=s;
    while(v != t){
        for(int id : g[v]) if(!(id&1) && flowOn(id) > 0){ // прямое ребро с потоком
            path.push_back(id); v = e[id].to; break;
        }
    }
    int mn = минимум потока по рёбрам path;
    for(int id : path) уменьшить flowOn(id) на mn; // "снять" путь
    вывести path с величиной mn;
}

Чтобы знать пущенный поток, храните исходные пропускные orig_cap и считайте flow = orig_cap - cap для прямых рёбер. Декомпозиция работает за $O(VE)$: число путей $\le E$, каждый ищется за $O(V)$.