一、网络流模型
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 最大流量算法，网络中的初始流量为零，沿着任意从起点到终点（且不含有饱和的正向边或空逆向边）的增广路增大流量，直到网络中不存在这样的路径为止。
网友评论