公司新闻

通道各有运输上限时怎样求整个地图的最大流量:规则练习第02例

2026-11-09 1

多条路线可以同时运送物品,但共享某条通道时总量仍受它的容量限制。把每条路线的瓶颈直接相加,容易把共享通道重复使用。

起点为房间零,终点为房间五,有向通道容量为整数。每次沿仍有剩余容量的路径增送瓶颈值,同时允许在后续通过反向剩余通道撤回之前的一部分分配;直到找不到增广路为止。

本例输入与约定

原通道及容量为[[0, 1, 5], [0, 2, 9], [0, 5, 9], [1, 3, 6], [1, 4, 9], [1, 5, 3], [2, 3, 6], [2, 4, 9], [2, 5, 3], [3, 4, 4], [3, 5, 8], [4, 5, 9]];每条边只表示一个方向。

完整计算记录

每次增广路径与增加量: [[0, 5], 9] [[0, 1, 5], 3] [[0, 2, 5], 3] [[0, 1, 3, 5], 2] [[0, 2, 3, 5], 6] 原边 | 最终流量/容量 0→1 | 5/5 0→2 | 9/9 0→5 | 9/9 1→3 | 2/6 1→4 | 0/9 1→5 | 3/3 2→3 | 6/6 2→4 | 0/9 2→5 | 3/3 3→4 | 0/4 3→5 | 8/8 4→5 | 0/9 最大总量23;一个最小切分的起点侧房间[0]。

表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。

复核方法与适用范围

除了起终点,每个房间的流入与流出必须相等,每条原通道上的流量不能超过容量。再找一组包含起点而不含终点的房间,合计离开这组的容量;最小这样的切分容量应等于最大流量。

这是静态容量网络,不计算运输耗时、先后排队或途中损耗。容量若是每拍上限,最大流量也只是对应模型下的吞吐量;不能直接把它当作首件物品到达需要的时间。

练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。