多条路线可以同时运送物品,但共享某条通道时总量仍受它的容量限制。把每条路线的瓶颈直接相加,容易把共享通道重复使用。
起点为房间零,终点为房间五,有向通道容量为整数。每次沿仍有剩余容量的路径增送瓶颈值,同时允许在后续通过反向剩余通道撤回之前的一部分分配;直到找不到增广路为止。
本例输入与约定
原通道及容量为[[0, 1, 4], [0, 2, 9], [0, 4, 6], [0, 5, 6], [1, 3, 7], [1, 4, 6], [1, 5, 3], [2, 3, 5], [2, 5, 9], [3, 4, 2], [3, 5, 9]];每条边只表示一个方向。
完整计算记录
每次增广路径与增加量: [[0, 5], 6] [[0, 1, 5], 3] [[0, 2, 5], 9] [[0, 1, 3, 5], 1] 原边 | 最终流量/容量 0→1 | 4/4 0→2 | 9/9 0→4 | 0/6 0→5 | 6/6 1→3 | 1/7 1→4 | 0/6 1→5 | 3/3 2→3 | 0/5 2→5 | 9/9 3→4 | 0/2 3→5 | 1/9 最大总量19;一个最小切分的起点侧房间[0, 4]。
表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。
复核方法与适用范围
除了起终点,每个房间的流入与流出必须相等,每条原通道上的流量不能超过容量。再找一组包含起点而不含终点的房间,合计离开这组的容量;最小这样的切分容量应等于最大流量。
这是静态容量网络,不计算运输耗时、先后排队或途中损耗。容量若是每拍上限,最大流量也只是对应模型下的吞吐量;不能直接把它当作首件物品到达需要的时间。
练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。
