Dinic 模板

dinic.cpp

#define SZ(x) (int)(x).size()
const int N = 2e3+5;

struct arc{ //据说数据量大时，vector存图比前向星块
    int v;
    ll residual_capacity;
    int next;
};



vector<arc> E;
vi head(N, -1); //为了避免忘记初始化

void add_arc(int u, int v, ll c) {
    E.pb({v, c, head[u]});
    head[u] = SZ(E) - 1;
    E.pb({u, 0, head[v]});
    head[v] = SZ(E) - 1;
}

int s, t;
int level[N];
bool bfs() {
    memset(level, -1, sizeof level);
    level[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = head[u]; i != -1; i = E[i].next) {
            int v = E[i].v;
            if (E[i].residual_capacity > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                if (v == t) return true; // 这里是一个优化
                que.push(v);
            }
        }
    }
    return false;
}

vi cur(N);

ll dfs(int u, ll rc) {
    if (u == t) return rc;
    int total = 0;
    for (int &i = cur[u]; i != -1; i = E[i].next) {
        int v = E[i].v;
        if (level[u] < level[v] && E[i].residual_capacity > 0) {
            auto tmp = dfs(v, min(rc, E[i].residual_capacity));
            if (tmp > 0) {
                E[i].residual_capacity -= tmp;
                E[i^1].residual_capacity += tmp;
                total += tmp; //多路增广
                rc -= tmp;
                if (rc == 0) break;
            }
        }
    }
    return total;
}

ll dinic(int n) {
    ll ans = 0;
    while (bfs()) {
        cur = head;
        for (int f; f = dfs(s, INT_MAX); ans += f);
    }
    return ans;
}