03-网络与最大流量

题目：

下图标出了某地区的运输路径管道，各节点之间的运输能力如下图所示。那么，从节点①到节点⑥的最大运输能力（流量）可以达到多少万吨/小时？

解析：

    做这个题之前，我们首先要明白一个问题，如果有三节粗细不同的管道连接起来，那么整个管道的最大流量受限制的是在哪个管道上？

    如图所示：

    ABC三个管道，拼接在一起，那么水的流量最大时，那根管道限制了最大水流量？ 毫无疑问是C对吧，如果C管道能流5立方/h的水，那么整个ABC管道的最大流量就是5立方/h。

    当然水流的快慢还跟压力有关，这里我们就不去考虑压力了。

    对于本题，我们可以依次分析每一个路径上的最大流量，然后将最大流量“抽取”出来，依次累加，就可以得到1到6的最大流量了。

    步骤1：

    我们就先挑选最大的，依次“抽取”这个最大流量，我们抽取路径1356上的“最大”流量10.

抽取后

再次抽取一个最大的，抽取1256上的最大流量6。

抽取后

再抽取146上的最大流量5

抽取后

再次抽取14356路径上的最大流量1

抽取后

再次抽取14256上最大流量1,

抽取后的图示

此时，虽然部分节点之间还有流量，但是无法从1到6连通了，也就是剩下了残余的流量，无法使用。

最终结果，1到6的最大运算能力为

    10 + 6 + 5 + 1 + 1 = 23