Dinic法最大流

template<class T = int>
struct Flow {
    int n;
    T INF;
    struct Edge {
        int v;
        T f;
    };
    std::vector<std::vector<int>> g;
    std::vector<int> d, cur;
    std::vector<Edge> e;
    Flow(int n, T INF = 1e9): n(n), g(n), INF(INF){}
    void add(int a, int b, T c) {
        g[a].push_back(e.size());
        e.push_back({b, c});
        g[b].push_back(e.size());
        e.push_back({a, 0});
    }
    bool bfs(int s, int t) {
        std::queue<int> q;
        d.assign(n, -1);
        d[s] = 0;
        q.push(s);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (int idx: g[u]) {
                auto [v, f] = e[idx];
                if (d[v] == -1 && f) {
                    d[v] = d[u] + 1;
                    if (v == t) return 1;
                    q.push(v);  
                }
            }
        }
        return 0;
    }
    T find(int u, int t, T limit) {
        if (u == t) return limit;
        T flow = 0;
        for (int &i = cur[u]; i < g[u].size() && flow < limit; ++i) {
            int idx = g[u][i];
            auto [v, f] = e[idx];
            if (d[v] == d[u] + 1 && f) {
                T get = find(v, t, std::min(f, limit - flow));
                if (!get) d[v] = -1;
                e[idx].f -= get, e[idx ^ 1].f += get, flow += get;
            }
        }
        return flow;
    }
    T run(int s, int t) {
        T res = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            res += find(s, t, INF);
        }
        return res;
    }
};