某运输网络图(见下图)有A~E五个结点,结点之间标有运输方向箭线,每条箭线旁标有两个数字,前一个是单位流量的运输费用,后一个是该箭线所允许的单位时间内的流量上限。从结点A到E可以有多种分配运输量的方案。如果每次都选择最小费用的路径来分配最大流量,则可以用最小总费用获得最大总流量的最优运输方案。该最优运输方案中,所需总费用和达到的总流量分别为(60,11)。

最小费用最大流是网络流优化领域的经典问题,核心目标是在实现源点到汇点最大流量传输的同时,使总费用最低。这类问题的通用解决思路采用贪心迭代策略:每次从源点到汇点中筛选出单位运输费用最低的可行路径,在该路径上分配其能承载的最大流量,也就是路径上所有边的流量上限中的最小值,之后更新路径各边的剩余可通行容量,若某边容量耗尽则暂时不再参与后续路径匹配。重复上述步骤,直到源点与汇点之间不存在可行路径为止,此时累加的流量总和即为最大总流量,各路径的流量与对应单位费用乘积的总和就是最小总费用。
该方法可广泛应用于物流资源调配、通信网络流量规划、供应链生产调度等场景,其底层融合了增广路径搜索与贪心决策的逻辑,实际应用中还可通过构建剩余网络、设置反向边等方式,更高效地处理流量的动态调整与路径重寻,进一步优化算法的适用范围与运行效率。
此题考察网络与最大流量相关概念。
本题要求从结点1到结点6的最大流量,其实就是把从结点1到结点6所有的路径找出来,然后把每条路径的流量进行累加。
因为ACBE路径总的最小费用最小,所以根据题意优先计算。
路径ACBE的最大流量为5万吨,计算过后,该路径上各段流量应都减少5万吨。从而BC之间将断开,AC之间的剩余流量是3万吨,BE之间的剩余流量是2万吨(如下图)。

其次ABE上费用最小,所以抽取路径ABE上的最大流量,路径ABE的最大流量为2万吨,计算过后,该路径上各段流量应都减少2万吨。从而BE之间将断开,AB之间的剩余流量是8万吨(如下图)。

然后抽取路径ACDE上的最大流量,路径ACDE的最大流量为3万吨,计算过后,该路径上各段流量应都减少3万吨。从而AC之间将断开,CD之间的剩余流量是7万吨,DE之间的剩余流量是1万吨(如下图)。

然后抽取 ABDE 上的最大流量,计算过后,该路径上各段流量应都减少1万吨,从而DE之间将断开,至此起点到终点已经没有通路,所以算法结束。

所以A到E的最大流量为5+2+3+1=11,总费用为5*4+2*5+3*6+1*12=60。
答案为C选项。
