わたしの部屋

1
import java.util.*;
2

3
public class MaxFlow {
4

5
    /**
6
     * 边对象：存储终点、容量、实际流量，以及反向边的引用指针。
7
     */
8
    static class Edge {
9
        int to;
10
        int cap;
11
        int flow;
12
        Edge rev; // 指向与之绑定的反向边，用于快速“退水”
13

14
        Edge(int to, int cap) {
15
            this.to = to;
16
            this.cap = cap;
17
            this.flow = 0;
18
        }
19

20
        // 计算这条边的富余空间（残量）
21
        int residual() {
22
            return cap - flow;
23
        }
24
    }
25

26
    private final int n;
27
    private final List<Edge>[] adj;
28

29
    @SuppressWarnings("unchecked")
30
    public MaxFlow(int n) {
31
        this.n = n;
32
        this.adj = new ArrayList[n];
33
        for (int i = 0; i < n; i++) {
34
            adj[i] = new ArrayList<>();
35
        }
36
    }
37

38
    /**
39
     * 添加一条从 u 到 v 容量为 cap 的有向水管。
40
     * 同时自动在底层创建一条容量为 0 的反向退水管道 v -> u。
41
     */
42
    public void addEdge(int u, int v, int cap) {
43
        Edge forward = new Edge(v, cap);
44
        Edge backward = new Edge(u, 0); // 反向边初始容量为 0
45
        forward.rev = backward;
46
        backward.rev = forward;
47
        adj[u].add(forward);
48
        adj[v].add(backward);
49
    }
50

51
    /**
52
     * BFS 标号法：在残量网络中寻找 s 到 t 的最短增广路。
53
     * parent[v] 数组用来记录到达 v 的那条管道，方便我们在寻路成功后回溯。
54
     * @return 寻找到的增广路上的瓶颈流量；若 s 与 t 已断开则返回 0
55
     */
56
    private int bfs(int s, int t, Edge[] parent) {
57
        boolean[] visited = new boolean[n];
58
        Queue<Integer> queue = new LinkedList<>();
59

60
        visited[s] = true;
61
        queue.offer(s);
62

63
        while (!queue.isEmpty()) {
64
            int u = queue.poll();
65
            for (Edge e : adj[u]) {
66
                // 如果这个邻居没有访问过，且管道还可以继续送水（残量 > 0）
67
                if (!visited[e.to] && e.residual() > 0) {
68
                    visited[e.to] = true;
69
                    parent[e.to] = e; // 贴上便利贴：记录前驱边
70

71
                    if (e.to == t) {
72
                        // 成功探索到终点，顺着前驱链回溯，计算整条路上的瓶颈限制
73
                        int bottleneck = Integer.MAX_VALUE;
74
                        for (int v = t; v != s; ) {
75
                            Edge pe = parent[v];
76
                            bottleneck = Math.min(bottleneck, pe.residual());
77
                            v = pe.rev.to; // 顺着反向边找回上一个起点
78
                        }
79
                        return bottleneck;
80
                    }
81
                    queue.offer(e.to);
82
                }
83
            }
84
        }
85
        return 0; // s 到 t 在当前导向图中已无法连通
86
    }
87

88
    /**
89
     * Edmonds-Karp 最大流算法主循环。
90
     * 反复用 BFS 寻路并推流，直到找不到增广路为止。
91
     */
92
    public int edmondsKarp(int s, int t) {
93
        int maxFlow = 0;
94
        Edge[] parent = new Edge[n];
95

96
        while (true) {
97
            int bottleneck = bfs(s, t, parent);
98
            if (bottleneck == 0) break; // 找不到路了，宣告结束
99

100
            // 沿着刚刚贴好标签的增广路进行“推流与对冲”：
101
            // 正向边流量增加，反向边流量同步减少
102
            for (int v = t; v != s; ) {
103
                Edge e = parent[v];
104
                e.flow += bottleneck;
105
                e.rev.flow -= bottleneck; // 对冲更新
106
                v = e.rev.to;
107
            }
108

109
            maxFlow += bottleneck;
110
        }
111

112
        return maxFlow;
113
    }
114

115
    /** 打印每条正向管道的最终水流量。 */
116
    public void printFlow(String[] name) {
117
        for (int u = 0; u < n; u++) {
118
            for (Edge e : adj[u]) {
119
                if (e.cap > 0) {
120
                    System.out.printf("%s -> %s : f=%d / c=%d (残量=%d)%n",
121
                            vertexName(name, u), vertexName(name, e.to),
122
                            e.flow, e.cap, e.residual());
123
                }
124
            }
125
        }
126
    }
127

128
    private String vertexName(String[] name, int id) {
129
        if (name != null && id < name.length) return name[id];
130
        return String.valueOf(id);
131
    }
132

133
    public static void main(String[] args) {
134
        // 顶点编号：s=0, A=1, B=2, t=3
135
        String[] name = {"s", "A", "B", "t"};
136
        MaxFlow mf = new MaxFlow(4);
137
        mf.addEdge(0, 1, 2);  // s -> A
138
        mf.addEdge(0, 2, 1);  // s -> B
139
        mf.addEdge(1, 2, 1);  // A -> B
140
        mf.addEdge(1, 3, 1);  // A -> t
141
        mf.addEdge(2, 3, 2);  // B -> t
142

143
        System.out.println("max flow: " + mf.edmondsKarp(0, 3));
144
        mf.printFlow(name);
145
    }
146
}

1
max flow: 3
2
s -> A : f=2 / c=2 (残量=0)
3
s -> B : f=1 / c=1 (残量=0)
4
A -> B : f=1 / c=1 (残量=0)
5
A -> t : f=1 / c=1 (残量=0)
6
B -> t : f=2 / c=2 (残量=0)