Как реализовать алгоритм Эдмондса-Карпа (BFS) для максимального потока и почему он O(V·E²)?

Идея: Эдмондс-Карп — это Форд-Фалкерсон, где увеличивающий путь всегда берётся как кратчайший по числу рёбер (BFS в остаточной сети). Это убирает патологии и даёт полиномиальную оценку.

#include <bits/stdc++.h>
using namespace std;
struct Edge { int to, cap; };
vector<Edge> e;
vector<vector<int>> g;
int n;

void add_edge(int u, int v, int cap){
    g[u].push_back(e.size()); e.push_back({v, cap});
    g[v].push_back(e.size()); e.push_back({u, 0});
}

int maxflow(int s, int t){
    int flow = 0;
    while(true){
        vector<int> par(n, -1); // индекс ребра, по которому пришли
        par[s] = -2;
        queue<int> q; q.push(s);
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(int id : g[v]){
                int to = e[id].to;
                if(par[to]==-1 && e[id].cap>0){
                    par[to]=id; q.push(to);
                }
            }
        }
        if(par[t]==-1) break; // путей нет — поток максимален
        // минимум остаточной по пути
        int push = INT_MAX;
        for(int v=t; v!=s; ){ int id=par[v]; push=min(push,e[id].cap); v=e[id^1].to; }
        for(int v=t; v!=s; ){ int id=par[v]; e[id].cap-=push; e[id^1].cap+=push; v=e[id^1].to; }
        flow += push;
    }
    return flow;
}

Почему $O(VE^2)$. Можно доказать, что расстояние от $s$ до любой вершины в остаточной сети не убывает по ходу алгоритма. Ребро называется «критическим», когда именно оно даёт минимум на увеличивающем пути (после пуска оно исчезает). Каждое ребро может стать критическим не более $O(V)$ раз. Рёбер $O(E)$, значит всего итераций (увеличивающих путей) — $O(VE)$. Каждый BFS стоит $O(E)$. Итог — $O(VE^2)$ по времени, $O(V+E)$ по памяти.

Граблю проверьте: при больших пропускных используйте long long для push и flow, иначе переполнение.