封装成一个类。连续最短路算法：Dijkstra/SPFA + DFS 多路增广（precondition：初始网络中没有负圈）

【模板】最小费用最大流.cpp

class MCMF {
    struct arc {
        const int to, next, cost;
        mutable int cap;
    };
    const int n_node;
    vi head;
    vector<arc> e;

    mutable vi d;
    bool dijkstra(int s, int t) const {
        const int inf = 10000;
        d.assign(n_node, inf);
        pq<pii, greater<pii>> que;
        que.push({d[s] = 0, s});
        while (!que.empty()) {
            auto top = que.top();
            que.pop();
            int u = top.second;
            if (d[u] != top.first) continue;
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to;
                if (e[i].cap > 0 && d[v] > d[u] + e[i].cost) {
                    d[v] = d[u] + e[i].cost;
                    que.push({d[v], v});
                }
            }
        }
        return d[t] < inf;
    }
    mutable vi cur;
    mutable vb vis;
    int dfs(int u, int flow, int t) const {
        if (u == t) return flow;
        vis[u] = true; // "vis[u] = true;" 不能写在 "if (u == t) return flow;" 之前！
        int pushed = 0;
        for (int &i = cur[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (!vis[v] && e[i].cap && d[v] == d[u] + e[i].cost) {
                int tmp = dfs(v, min(flow - pushed, e[i].cap), t);
                if (tmp) {
                    e[i].cap -= tmp;
                    e[i ^ 1].cap += tmp;
                    pushed += tmp;
                    if (flow == pushed) break;
                }
            }
        }
        vis[u] = false;
        return pushed;
    }
public:
    explicit MCMF(int n_node) : n_node(n_node) {
        head.assign(n_node, -1);
    }
    void add_edge(int u, int v, int cost, int cap) {
        e.pb({v, head[u], cost, cap});
        head[u] = SZ(e) - 1;
        e.pb({u, head[v], -cost, 0});
        head[v] = SZ(e) - 1;
    }
    ll mcmf(int s, int t) const {
        ll ans = 0;
        vis.assign(n_node, false);
        while (dijkstra(s, t)) {
            cur = head;
            while (true) {
                int f = dfs(s, INT_MAX, t);
                if (f) ans += f * d[t];
                else break;
            }
        }
        return ans;
    }
};