MCMF

#include <bits/stdc++.h>
using namespace std;

int N, M;

typedef pair<int, int> pii;
const int INF = 1e9;
typedef struct MCMF {
    typedef struct EDGE {
        int there, cap, cost, rev;

        EDGE() : there(0), cap(0), cost(0), rev(0) {}
        EDGE(int there, int cap, int cost, int rev) : there(there), cap(cap), cost(cost), rev(rev) {}
    };

    int N;
    vector<vector<EDGE>> ADJ;
    vector<int> R, INQ, C, I;

    MCMF() : N(0) {}
    MCMF(int N) : N(N) { ADJ.resize(N + 1); R.resize(N + 1); INQ.resize(N + 1);  C.resize(N + 1); I.resize(N + 1); }

    void connect_edge(int index1, int index2, int cap, int cost) {
        ADJ[index1].push_back(EDGE(index2, cap, cost, ADJ[index2].size()));
        ADJ[index2].push_back(EDGE(index1, 0, -cost, ADJ[index1].size() - 1));
    }
    bool SPFA(int src, int sink) {
        queue<int> Q;   Q.push(src);
        fill(R.begin(), R.end(), -1);   R[src] = 0;
        fill(C.begin(), C.end(), -1);   C[src] = 0;
        fill(INQ.begin(), INQ.end(), 0);    INQ[src] = 1;
        while (Q.size()) {
            int here = Q.front();   Q.pop();
            INQ[here] = 0;
            for (int i = 0; i < ADJ[here].size(); i++) {
                auto e = ADJ[here][i];
                if (e.cap > 0 && (C[e.there] == -1 || C[e.there] > C[here] + e.cost)) {
                    C[e.there] = C[here] + e.cost;  R[e.there] = here;  I[e.there] = i;
                    if (!INQ[e.there]) INQ[e.there] = 1, Q.push(e.there);
                }
            }
        }
        if (C[sink] == -1) return false;
        return true;
    }

    pii mcmf(int src, int sink) {
        pii ret = { 0, 0 };
        while (SPFA(src, sink)) {
            int flow = INF, cost = 0;
            for (int here = sink; here != src; here = R[here]) flow = min(flow, ADJ[R[here]][I[here]].cap);
            for (int here = sink; here != src; here = R[here]) {
                auto &e = ADJ[R[here]][I[here]];
                cost += e.cost * flow;
                e.cap -= flow;
                ADJ[e.there][e.rev].cap += flow;
            }

            ret.first += flow, ret.second += cost;
        }
        return ret;
    }
};