网络流基础

int maxFlow(int[][] capacity, int s, int t) {
    int n = capacity.length;
    int[][] residual = new int[n][n]; // 残余网络
    for (int i = 0; i < n; i++) residual[i] = capacity[i].clone();

    int flow = 0;
    int[] parent = new int[n];

    while (bfs(residual, s, t, parent)) {
        // 找增广路上的最小残余容量
        int pathFlow = Integer.MAX_VALUE;
        for (int v = t; v != s; v = parent[v]) {
            pathFlow = Math.min(pathFlow, residual[parent[v]][v]);
        }
        // 更新残余网络
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            residual[u][v] -= pathFlow;
            residual[v][u] += pathFlow; // 反向边
        }
        flow += pathFlow;
    }
    return flow;
}

boolean bfs(int[][] residual, int s, int t, int[] parent) {
    Arrays.fill(parent, -1);
    parent[s] = s;
    Queue<Integer> q = new LinkedList<>();
    q.offer(s);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v = 0; v < residual.length; v++) {
            if (parent[v] == -1 && residual[u][v] > 0) {
                parent[v] = u;
                if (v == t) return true;
                q.offer(v);
            }
        }
    }
    return false;
}

// 时间 O(V²E)，实际远快于此
int dinic(int s, int t) {
    int flow = 0;
    while (bfsLevel(s, t)) { // 建层次图
        Arrays.fill(iter, 0);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}