XCPC 竞赛模板

struct Graph {
    struct Edge {
        int v; long w;
        Edge(int v = 0, long w = 0) : v(v), w(w) {}
    };
    int S, T, cur[N], d[N];
    vector<Edge> edges;
    vector<int> G[N];
    void addedge(int u, int v, long w) {
        edges.emplace_back(v, w);
        G[u].emplace_back(edges.size() - 1);
        edges.emplace_back(u, 0);
        G[v].emplace_back(edges.size() - 1);  
    }
    bool bfs(void) {
        memset(d, -1, sizeof d);
        queue<int> q; q.push(S); d[S] = 1;
        while (!q.empty()) {
            const int u = q.front(); q.pop();
            for (const int id : G[u]) {
                Edge &e = edges[id];
                if (e.w && d[e.v] == -1) {
                    d[e.v] = d[u] + 1; q.push(e.v);
                    if (e.v == T) return true;
                }
            }
        }
        return false; 
    }
    long dinic(int x, long res) {
        if (x == T) return res;
        long flow = 0;
        for (int i = cur[x]; i < (int)G[x].size() && res; ++i) {
            cur[x] = i;
            Edge &e = edges[G[x][i]];
            const long c = min(res, e.w);
            if (d[e.v] == d[x] + 1 && c) {
                long k = dinic(e.v, c); flow += k; res -= k;
                e.w -= k; edges[G[x][i] ^ 1].w += k;
            }
        }
        if (!flow) d[x] = -1;
        return flow; 
    }
    long maxFlow(int s, int t) {
        S = s, T = t;
        long mxf = 0;
        while (bfs()) {
            memset(cur, 0, sizeof cur);
            while (long flow = dinic(S, 1e18)) mxf += flow;
        }
        return mxf;
    }
} G;