网络流 java算法

网络流是一种图论算法，用于解决最大流问题。Java中可以使用Dinic算法或者Edmonds-Karp算法实现网络流。

Dinic算法的基本思想是通过多次增广路径来求解最大流，时间复杂度为O(V^2E)。Edmonds-Karp算法则是在BFS的基础上进行增广，时间复杂度为O(VE^2)。

以下是Java实现Dinic算法的示例代码：

import java.util.*;

public class Dinic {
    static int N = 510, M = 100010, INF = 0x3f3f3f3f;
    static int n, m, S, T;
    static int h[] = new int[N], e[] = new int[M], f[] = new int[M], ne[] = new int[M], idx;
    static int d[] = new int[N], cur[] = new int[N];
    static boolean st[] = new boolean[N];

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        S = 1;
        T = n;
        Arrays.fill(h, -1);
        while (m-- > 0) {
            int a = scan.nextInt(), b = scan.nextInt(), c = scan.nextInt();
            add(a, b, c);
        }
        System.out.println(dinic());
    }

    static void add(int a, int b, int c) {
        e[idx] = b;
        f[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
        e[idx] = a;
        f[idx] = 0;
        ne[idx] = h[b];
        h[b] = idx++;
    }

    static boolean bfs() {
        Arrays.fill(d, -1);
        Queue<Integer> q = new LinkedList<>();
        q.offer(S);
        d[S] = 0;
        cur[S] = h[S];
        while (!q.isEmpty()) {
            int t = q.poll();
            for (int i = h[t]; i != -1; i = ne[i]) {
                int ver = e[i];
                if (d[ver] == -1 && f[i] > 0) {
                    d[ver] = d[t] + 1;
                    cur[ver] = h[ver];
                    if (ver == T) return true;
                    q.offer(ver);
                }
            }
        }
        return false;
    }

    static int find(int u, int limit) {
        if (u == T) return limit;
        int flow = 0;
        for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
            cur[u] = i;
            int ver = e[i];
            if (d[ver] == d[u] + 1 && f[i] > 0) {
                int t = find(ver, Math.min(f[i], limit - flow));
                if (t == 0) d[ver] = -1;
                f[i] -= t;
                f[i ^ 1] += t;
                flow += t;
            }
        }
        return flow;
    }

    static int dinic() {
        int r = 0, flow;
        while (bfs()) while ((flow = find(S, INF)) != 0) r += flow;
        return r;
    }
}