如何在多源流网络中找到最大流量? [英] 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屋!
查看全文