Maximum Flow Minimum Cost implementation with SPFA

MCMF.h

#include <cstdio>

#define min(a, b) a < b ? a : b

using namespace std;

template<typename lt = long, typename sz = size_t>
struct MCMF {
    static constexpr lt INF = 1e9;
    static constexpr lt MAX_NODES = 1e6 + 5;

    struct Edge {
        sz from;
        sz to;
        sz next;
        lt cap;
        lt cost;

        Edge(): from(0), to(0), next(0), cap(0), cost(0) {}

        Edge(sz f, sz t, sz n, lt cp, lt cs)
        : from(f), to(t), next(n), cap(cp), cost(cs) {}
    };

    struct Solution {
        lt maxFlow;
        lt cost;
    };

    sz N;
    sz count;
    Solution sol;
    sz* head; // head
    lt* pre;
    lt* dis;
    sz* vis;
    sz* path;
    sz* q; // queue
    Edge* e; // edges

    MCMF(sz maxNodes = MCMF::MAX_NODES) {
        N = maxNodes+1;
        count = 0;

        head = new sz[MCMF::MAX_NODES];
        for (sz i = 0; i < maxNodes; i++) head[i] = -1;
        pre = new lt[MCMF::MAX_NODES];
        dis = new lt[MCMF::MAX_NODES];
        vis = new sz[MCMF::MAX_NODES];
        path = new sz[MCMF::MAX_NODES];
        q = new sz[MCMF::MAX_NODES];
        e = new Edge[MCMF::MAX_NODES << 2];
    }

    ~MCMF() {
        delete head;
        delete pre;
        delete dis;
        delete vis;
        delete path;
        delete q;
        delete e;
    }

    inline void addDirect(sz from, sz to, lt cap, lt cost) {
        e[count] = Edge(from, to, head[from], cap, cost);
        head[from] = count++;
    }

    inline void add(sz from, sz to, sz cap, lt cost) {
        addDirect(from, to, cap, cost);
        addDirect(to, from, 0, -cost);
    }

    bool spfa(sz s, sz t) {
        for (sz i = 0; i < N; i++) dis[i] = MCMF::INF;
        for (sz j = 0; j < N; j++) {
            pre[j] = -1;
            vis[j] = 0;
        }
        dis[s] = 0;
        sz h = 0;
        q[h++] = s;
        vis[s] = 1;
        while (h) {
            sz u = q[--h];
            for (sz i = head[u]; i != -1; i = e[i].next) {
                sz v = e[i].to;
                if (e[i].cap > 0 && dis[v] > dis[u] + e[i].cost) {
                    dis[v] = dis[u] + e[i].cost;
                    pre[v] = u;
                    path[v] = i;
                    if (!vis[v]) {
                        vis[v] = 1;
                        q[h++] = v;
                    }
                }
            }
            vis[u] = 0;
        }

        return pre[t] != -1;
    }

    void calc(sz s, sz t) {
        sz u;
        lt flow = MCMF::INF;
        for (u = t; u != s; u = pre[u])
            flow = min(flow, e[path[u]].cap);
        sol.maxFlow += flow;
        for (u = t; u != s; u = pre[u]) {
            e[path[u]].cap -= flow;
            e[path[u]^1].cap += flow;
            sol.cost += flow * e[path[u]].cost;
        }
    }

    Solution solve(sz s, sz t) {
        sol.maxFlow = 0;
        sol.cost = 0;
        while (spfa(s, t)) calc(s, t);
        
        return sol;
    }
};