Как реализовать алгоритм Диница со слоистой сетью и блокирующим потоком?

Идея Диница. Алгоритм работает фазами. В каждой фазе:

1. BFS от $s$ строит уровни level[v] = кратчайшее расстояние в остаточной сети. Если до $t$ не дошли — поток максимален, стоп.
2. DFS ищет блокирующий поток в слоистой сети (идём только по рёбрам $level[v]+1 = level[to]$). «Блокирующий» = насыщаем пути так, что ни одного пути $s\to t$ по слоистым рёбрам не осталось.

Ключ к скорости — указатель ptr[v]: при DFS из вершины $v$ не перебираем заново уже исчерпанные рёбра, а двигаем указатель. Это превращает один DFS-проход фазы в $O(VE)$.

struct Edge{int to; long long cap;};
vector<Edge> e; vector<vector<int>> g;
int n; vector<int> level, ptr;

void add_edge(int u,int v,long long c){
    g[u].push_back(e.size()); e.push_back({v,c});
    g[v].push_back(e.size()); e.push_back({u,0});
}
bool bfs(int s,int t){
    level.assign(n,-1); level[s]=0;
    queue<int> q; q.push(s);
    while(!q.empty()){int v=q.front();q.pop();
        for(int id:g[v]) if(level[e[id].to]==-1 && e[id].cap>0){
            level[e[id].to]=level[v]+1; q.push(e[id].to);}}
    return level[t]!=-1;
}
long long dfs(int v,int t,long long pushed){
    if(v==t||pushed==0) return pushed;
    for(int &cid=ptr[v]; cid<(int)g[v].size(); ++cid){
        int id=g[v][cid], to=e[id].to;
        if(level[v]+1!=level[to]||e[id].cap==0) continue;
        long long d=dfs(to,t,min(pushed,e[id].cap));
        if(d>0){ e[id].cap-=d; e[id^1].cap+=d; return d; }
    }
    return 0;
}
long long maxflow(int s,int t){
    long long flow=0;
    while(bfs(s,t)){
        ptr.assign(n,0);
        while(long long pushed=dfs(s,t,LLONG_MAX)) flow+=pushed;
    }
    return flow;
}

Асимптотика: $O(V^2 E)$ в общем случае, $O(E\sqrt{E})$ на единичных пропускных (двудольное паросочетание!), $O(E\sqrt{V})$ для сетей с единичными capacity. Память $O(V+E)$. Берите long long для cap и flow.