算法技术手册（原书第2 版）

218

｜

第

8

章

//

计算将要增加多少流量。结果等同于从汇点到源顶点计算路径上的最小值。

int increment = Integer.MAX_VALUE;

int v = sink;

while (previous[v] != -1) {

int unit = capacity[previous[v]][v] - flow[previous[v]][v];

if (unit < increment) { increment = unit; }

v = previous[v];

}

//

在路径上增加最少的流。

v = sink;

while (previous[v] != -1) {

flow[previous[v]][v] += increment; //

前向边。

flow[v][previous[v]] -= increment; //

不要忘了后向边。

v = previous[v];

}

return increment;

}

//

寻找流网络中

源顶点到汇点的增广路径。

public boolean search (int source, int sink) {

//

清除访问状态，

0

表示清除状态，

1

表示在队列中，

2

表示已访问。

for (int i = 0 ; i < numVertices; i++) { visited[i] = 0; }

//

创建一个循环队列来处理查找元素。

queue[0] ...