「补档计划」ISAP 和 HLPP 算法

const int MAXN = 1000010;

int gap[MAXN], h[MAXN];

struct Node {
    int v, f, index;
    Node(int v, int f, int index) : v(v), f(f), index(index) {}
};

std::vector<Node> edge[MAXN];

inline void addEdge(int u, int v, int f) {
    edge[u].push_back(Node(v, f, edge[v].size()));
    edge[v].push_back(Node(u, 0, edge[u].size() - 1));
}

inline int sap(int v, int flow, int s, int t, int n) {
    static int iter[MAXN];
    if (v == t) return flow;
    register int rec = 0;
    for (register int i = iter[v]; i < edge[v].size(); i++) {
        Node *p = &edge[v][i];
        if (h[v] == h[p->v] + 1) {
            register int ret = sap(p->v, std::min(flow - rec, p->f), s, t, n);
            p->f -= ret, edge[p->v][p->index].f += ret, iter[v] = i;
            if ((rec += ret) == flow) return flow; 
        }
    }
    if (!(--gap[h[v]])) h[s] = n;
    gap[++h[v]]++, iter[v] = 0;
    return rec;
}

inline int sap(int s, int t, int n) {
    register int ret = 0;
    gap[0] = n;
    while (h[s] < n) ret += sap(s, INT_MAX, s, t, n);
    return ret;
}

/*
 * created by xehoth on 27-04-2017
 */
#include <bits/stdc++.h>

const int MAXN = 1000015;

template<class T = int>
struct HighestLabelPreflowPush {

    struct Node {
        int u, v, index;
        T c, f;
        Node(int u, int v, int c, const T &f, const T &index) : u(u), v(v), c(c), f(f), index(index) {}
    };

    std::vector<Node> edge[MAXN];
    std::vector<int> q[MAXN];
    int dis[MAXN], cnt[MAXN + 1], pos, n;
    T exc[MAXN];
    bool act[MAXN];

    inline void addEdge(int u, int v, const T &c) {
        edge[u].push_back(Node(u, v, c, 0, edge[v].size()));
        if (u == v) edge[u].back().index++;
        edge[v].push_back(Node(v, u, 0, 0, edge[u].size() - 1));
    }

    inline void enqueue(int v) {
        if (!act[v] && exc[v] > 0 && dis[v] < n) {
            act[v] = true, q[dis[v]].push_back(v);
            pos = std::max(pos, dis[v]);
        }
    }

    inline void push(Node &e) {
        register T amt = std::min(exc[e.u], e.c - e.f);
        if (dis[e.u] == dis[e.v] + 1 && amt > 0) {
            e.f += amt;
            edge[e.v][e.index].f -= amt;
            exc[e.v] += amt;
            exc[e.u] -= amt;
            enqueue(e.v);
        }
    }

    inline void gap(int k) {
        for (register int v = 0; v < n; v++) {
            if (dis[v] >= k) {
                cnt[dis[v]]--;
                dis[v] = std::max(dis[v], n);
                cnt[dis[v]]++;
                enqueue(v);
            }
        }
    }

    inline void relabel(int v) {
        cnt[dis[v]]--, dis[v] = n;
        for (register int i = 0; i < edge[v].size(); i++) {
            Node *e = &edge[v][i];
            if (e->c - e->f > 0) dis[v] = std::min(dis[v], dis[e->v] + 1);
        }
        cnt[dis[v]]++;
        enqueue(v);
    }

    inline void discharge(int v) {
        for (register int i = 0; i < edge[v].size(); i++) {
            Node &e = edge[v][i];
            if (exc[v] > 0) push(e);
            else break;
        }
        if (exc[v] > 0) {
            if (cnt[dis[v]] == 1) gap(dis[v]);
            else relabel(v);
        }
    }

    inline T getMaxflow(int s, int t) {
        pos = 0;
        for (register int i = 0; i < edge[s].size(); i++)
            exc[s] += edge[s][i].c;
        cnt[0] = n;
        enqueue(s);
        act[t] = true;
        while (pos >= 0) {
            if (!q[pos].empty()) {
                register int v = q[pos].back();
                q[pos].pop_back();
                act[v] = false;
                discharge(v);
            } else {
                pos--;
            }
        }
        return exc[t];
    }

    inline void init(int n) {
        memset(edge, 0, sizeof(std::vector<Node>) * (n + 1));
        memset(exc, 0, sizeof(T) * (n + 1));
        memset(q, 0, sizeof(std::vector<int>) * (n + 1));
        memset(act, 0, sizeof(bool) * (n + 1));
        memset(cnt, 0, sizeof(int) * (n + 2));
        memset(dis, 0, sizeof(int) * (n + 1));
        this->n = n;
    }
};