多个源ans在最大floq和min cut中下沉

Question

我一直被困在这个问题中。假设我们有一个具有多个源节点和汇节点的流网络。我必须提供一个来自您自己的示例，并解释如何计算它的max-flow/min-cut。并且还必须找到示例网络的最小切入点

是的，我们可以通过使用虚拟信源和信宿来解决网络问题，但它到底是如何工作的，我不能理解……

Answer 1

这更多的是一个理论问题，所以对cs.stackexchange来说可能更好。但是你所说的是正确的--你添加了一个新的源和接收器。新的源s*将具有到原始图中所有源的有向边，并且每个源s的边(s*，s)的容量可以设置为无穷大(当然，流出s的流量受其向外的边的限制，因此这不会改变我们能够从s获得的流量)。类似地，为原始图中的所有接收器t添加一个具有边(t，t*)的新接收器t*。将容量设置为无穷大，因为从t出来的实际流量受到原始图中我们可以得到t的流量的限制。