如何在多源流网络中找到最大流量？ [英] How to find the maximum flow in a multi source flow network?

问题描述

如何将这种多源流网络转换为单源流网络并在其中找到最大流？

How to convert this multi source flow network in to single source flow network and find the maximum flow in that?

推荐答案

您创建一个虚拟源节点，称为 Source ，并从中绘制接近无限容量的有向边（例如，图的所有边的容量之和） 来源每个战车。结果图中的每个流都与原始多源图中的一一对应。

You create a dummy source node, called Source, and draw a directed edge of close-to-infinite-capacity (e.g. sum of capacities of all edges of the graph) from Source to each tank. Every flow in the resulting graph is in one-to-one correspondence with the original multi-source graph.

这篇关于如何在多源流网络中找到最大流量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！