最小费用最大流

package tgb.第三章;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class ok货物调配{
static int maxData = 0x7fffffff;
static Queue dl = new ArrayDeque();
static int head[] = new int[5001];
static long cost[] = new long [100001];
static int net[] = new int[100001];
static int to[] = new int[100001];
static long cap[] = new long [100001];
static long A[] = new long [100001];
static int cnt = 1;

static void add(int x, int y, int z, int c) {//容量，费用
    to[++cnt] = y;
    cost[cnt] = z;
    cap[cnt] = c;
    net[cnt] = head[x];
    head[x] = cnt;
}

static long  flow[] = new long [100001];
static int pre[] = new int[100001];
static int xb[] = new int[100001];
static int n, m;
static long  mflow = 0;
static long  mcost = 0;
static long  dis[] = new long [100001];
static long  f[] = new long [100001];

static int BFS(int s, int t) {
    Arrays.fill(dis, 0x7fffffff);
    Arrays.fill(f, 0);
    long INF = 0x7fffffff;
    // System.out.println(INF);
    while (!dl.isEmpty())
        dl.poll();
    for (int i = 1; i <= n; i++)
        pre[i] = -1;
    f[s] = 1;
    dis[s] = 0;
    pre[s] = 0;
    flow[s] = maxData;
    dl.add(s);
    while (!dl.isEmpty()) {
        int dd = dl.poll();
        f[dd] = 0;
        for (int i = head[dd]; i != 0; i = net[i]) {
            int tmp = to[i];
            if (cap[i] > 0 && dis[tmp] > dis[dd] + cost[i]) {
                dis[tmp] = dis[dd] + cost[i];
                pre[tmp] = dd;
                xb[tmp] = i;
                flow[tmp] = Math.min(flow[dd], cap[i]);
                if (f[tmp] == 0) {
                    f[tmp] = 1;
                    dl.add(tmp);
                }
            }
        }
    }
    if (dis[t] >= INF)
        return 0;
    return 1;
}

static void max_flow(int s, int t) {
    //提前结束?????
    while (BFS(s, t) != 0) {
        int k = t;
        while (k != s) {
            cap[xb[k]] -= flow[t];
            cap[xb[k] ^ 1] += flow[t];
            k = pre[k];
        }
        mflow += flow[t];
        mcost += flow[t] * dis[t];
        // System.out.println(flow[t]+" "+dis[t]);
    }
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int s, t;
    n = scanner.nextInt();
    m = scanner.nextInt();
    int D = 0;
    for (int i = 1; i <= n; i++) {
        A[i] = scanner.nextInt();
        D += A[i];
    }
    D /= n;
    s = 2 * n + 1;
    t = 2 * n + 2;
    for (int i = 1; i <= n; i++) {//费用 容量
        add(i + n, i, 0, (int) 1e9);
        add(i, i + n, 0, 0);
    }
    for (int i = 1; i <= n; i++) {//费用 容量
        if (A[i] >= D) {
            add(s, i, 0, (int) (A[i] - D));
            add(i, s, 0, 0);
        } else {
            add(i + n, t, 0, (int) (D - A[i]));
            add(t, i + n, 0, 0);
        }
    }
    while (m-- > 0) {
        int a, b, c;
        a = scanner.nextInt();
        b = scanner.nextInt();
        c = scanner.nextInt();
        add(a, b + n, c, (int) 1e9);
        add(b + n, a, -c, 0);
        int temp = a;
        a = b;
        b = temp;
        add(a, b + n, c, (int) 1e9);
        add(b + n, a, -c, 0);
    }
    n = 2 * n + 2;
    max_flow(s, t);
    System.out.println(mcost);
}

}