使用JAVA实现最小费用最大流

以下是使用Java实现最小费用最大流的示例代码，使用了Edmonds-Karp算法和SPFA算法：

import java.util.Arrays;
import java.util.LinkedList;

public class MinCostMaxFlow {
    private int n, m, s, t, maxFlow, minCost;
    private int[] head, dis, pre, flow, vis;
    private Edge[] edges;
    private LinkedList<Integer> queue;

    public MinCostMaxFlow(int n, int m, int s, int t) {
        this.n = n;
        this.m = m;
        this.s = s;
        this.t = t;
        this.head = new int[n + 1];
        this.edges = new Edge[m + 1];
        this.dis = new int[n + 1];
        this.pre = new int[n + 1];
        this.flow = new int[n + 1];
        this.vis = new int[n + 1];
        this.queue = new LinkedList<>();
        Arrays.fill(head, -1);
    }

    public void addEdge(int u, int v, int cap, int cost) {
        edges[m] = new Edge(u, v, cap, cost, head[u]);
        head[u] = m++;
        edges[m] = new Edge(v, u, 0, -cost, head[v]);
        head[v] = m++;
    }

    private boolean spfa() {
        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(vis, 0);
        dis[s] = 0;
        vis[s] = 1;
        flow[s] = Integer.MAX_VALUE;
        queue.add(s);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            vis[u] = 0;
            for (int i = head[u]; i != -1; i = edges[i].next) {
                int v = edges[i].v;
                if (edges[i].cap > 0 && dis[v] > dis[u] + edges[i].cost) {
                    dis[v] = dis[u] + edges[i].cost;
                    pre[v] = i;
                    flow[v] = Math.min(flow[u], edges[i].cap);
                    if (vis[v] == 0) {
                        vis[v] = 1;
                        queue.add(v);
                    }
                }
            }
        }
        return dis[t] != Integer.MAX_VALUE;
    }

    public void minCostMaxFlow() {
        while (spfa()) {
            int u = t;
            maxFlow += flow[t];
            minCost += dis[t] * flow[t];
            while (u != s) {
                edges[pre[u]].cap -= flow[t];
                edges[pre[u] ^ 1].cap += flow[t];
                u = edges[pre[u]].u;
            }
        }
    }

    static class Edge {
        int u, v, cap, cost, next;

        public Edge(int u, int v, int cap, int cost, int next) {
            this.u = u;
            this.v = v;
            this.cap = cap;
            this.cost = cost;
            this.next = next;
        }
    }
}

使用方法如下：

// 创建一个最小费用最大流对象
MinCostMaxFlow mcmf = new MinCostMaxFlow(n, m, s, t);

// 添加边
mcmf.addEdge(u, v, cap, cost);

// 求解最小费用最大流
mcmf.minCostMaxFlow();

// 最大流量
int maxFlow = mcmf.maxFlow;

// 最小费用
int minCost = mcmf.minCost;

其中，`n`表示点的数量，`m`表示边的数量，`s`表示源点，`t`表示汇点，`u`、`v`、`cap`、`cost`分别表示边的起点、终点、容量和费用。