最大流算法

一、网络流模型

1.1 网络流定义

一个流量网络是一张边的权重（这里称为容量）为正的加权有向图。该网络中通常有一个起点s和一个终点t，从起点s出发到达终点t的每一条边都有一个流量上限值（容量），网络流问题就是找到各种流量配置方案，使得每一条边的实际流量小于容量且每个顶点（除s、t）的净流量为0。

术语：
流入量：流向一个顶点的总流量（所有指向该顶点的边中的流量之和）
流出量：流出一个顶点的总流量（由该顶点指出的所有边中的流量之和）
净流量：流入量 - 流出量
最大s-t流量：给定一个s-t流量网络，找到一种流量配置方案，使得s->t的流量最大化

如下是用加权有向图表示网络流问题的模型：

1.2 API定义

流量边的API：

1-2-1 流量网络中边的API

流量边-源码：

public class FlowEdge {
    private final int v; // from
    private final int w; // to
    private final double capacity; // 容量
    private double flow; // 实际流量: v -> w
 
    public FlowEdge(int v, int w, double capacity) {
        if (capacity < 0.0)
            throw new IllegalArgumentException("Edge capacity must be non-negative");
        this.v = v;
        this.w = w;
        this.capacity = capacity;
        this.flow = 0.0;
    }
 
    public int from() {
        return v;
    }
 
    public int to() {
        return w;
    }
 
    public double capacity() {
        return capacity;
    }
 
    public double flow() {
        return flow;
    }
 
    public int other(int vertex) {
        if (vertex == v)
            return w;
        else if (vertex == w)
            return v;
        else
            throw new IllegalArgumentException("invalid endpoint");
    }
 
    /**
     * 返回边的流量
     * 
     * @return 如果顶点vertex是该边的起始顶点，返回边的实际流量
     *         如果顶点vertex是该边的结束顶点，返回边的剩余流量
     */
    public double residualCapacityTo(int vertex) {
        if (vertex == v)
            return flow; // backward edge
        else if (vertex == w)
            return capacity - flow; // forward edge
        else
            throw new IllegalArgumentException("invalid endpoint");
    }
 
    /**
     * 增加/减少边的流量
     * 如果顶点vertex是该边的起始顶点，则减少边的流量
     * 如果顶点vertex是该边的结束顶点，则增加边的流量
     */
    public void addResidualFlowTo(int vertex, double delta) {
        if (delta < 0.0)
            throw new IllegalArgumentException("Delta must be nonnegative");
 
        if (vertex == v)
            flow -= delta; // backward edge
        else if (vertex == w)
            flow += delta; // forward edge
        else
            throw new IllegalArgumentException("invalid endpoint");
 
        if (flow < 0.0)
            throw new IllegalArgumentException("Flow is negative");
        if (flow > capacity)
            throw new IllegalArgumentException("Flow exceeds capacity");
    }
 
    public String toString() {
        return v + "->" + w + " " + flow + "/" + capacity;
    }
}

流量网络的API：

1-2-2 流量网络API 1-2-3 流量网络示意图

流量网络的源码：

public class FlowNetwork {
    private final int V; // 顶点数
    private int E; // 边数
    private Bag<FlowEdge>[] adj; // adj[v]表示顶点v的所有出边
 
    public FlowNetwork(int V) {
        if (V < 0)
            throw new IllegalArgumentException("Number of vertices in a Graph must be nonnegative");
        this.V = V;
        this.E = 0;
        adj = (Bag<FlowEdge>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<FlowEdge>();
    }
    public FlowNetwork(In in) {
        int V = in.readInt();
        this(V);
        int E = in.readInt();
        if (E < 0)
            throw new IllegalArgumentException("number of edges must be nonnegative");
        for (int i = 0; i < E; i++) {
            int v = in.readInt(); // 起始顶点
            int w = in.readInt(); // 结束顶点
            double capacity = in.readDouble(); // 容量
            addEdge(new FlowEdge(v, w, capacity));
        }
    }
 
    public int V() {
        return V;
    }
    public int E() {
        return E;
    }
    public void addEdge(FlowEdge e) {
        int v = e.from();
        int w = e.to();
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }
    public Iterable<FlowEdge> adj(int v) {
        return adj[v];
    }
 
    // return list of all edges - excludes self loops
    public Iterable<FlowEdge> edges() {
        Bag<FlowEdge> list = new Bag<FlowEdge>();
        for (int v = 0; v < V; v++)
            for (FlowEdge e : adj(v)) {    //只保存顶点v的出边
                if (e.to() != v)
                    list.add(e);
            }
        return list;
    }
 
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " " + E + "\n");
        for (int v = 0; v < V; v++) {
            s.append(v + ":  ");
            for (FlowEdge e : adj[v]) {
                if (e.to() != v)
                    s.append(e + "  ");
            }
            s.append("\n");
        }
        return s.toString();
    }
}

二、最大流算法

2.1 Ford-Fulkerson算法

2.1.1 定义

Ford - Fulkerson 最大流量算法，网络中的初始流量为零，沿着任意从起点到终点（且不含有饱和的正向边或空逆向边）的增广路增大流量，直到网络中不存在这样的路径为止。