求教一个最大流相关的问题

[letianqiu]

给定一个 Network Flow 的 Graph，source，sink 以及 Graph 中任意两个 vertex: u 和 v。现在要求找出一个 cut，使得 u 和 source 属于同一个 set，v 和 sink 属于同一个 set，并且这个 cut 的 capacity 要求最小。

[fancy20]

最大流等于最小割，dinic, isap ？

[kilnyy]

建一个 vertex 超级源 和 source 与 u 连接，建一个 vertex 超级汇，和 sink 与 v 连接。这四条边 cost 设置为无穷大。然后正常求超级源汇之间的最小割。

[letianqiu]

@kilnyy 能解释一下这么做的原因吗？

[myk502]

蒟蒻试着解释一下。。
首先，最小割就是最大流的对偶问题，并且割边（连接两个割集的边）必须跑满
既然超级源到 source 超级源到 u 容量都为无穷大，那么肯定不是割边，那么 source 和 u 必定都属于 S 割点集。
同理，balabalala
所以 u v 会属于不同的两个割集
然后显然，添加的 4 条边不会影响最大流的流量（其实是我不会证明。。）
所以。。就好了

[myk502]

不是 cost， 是 capacity，这不是费用流

[myk502]

@letianqiu 老兄看你最近发的都是这种题，是不是在上算法课啊。最大流最小割建议看胡伯涛的 noi 冬令营论文。

[letianqiu]

@myk502 没错啊。最大流一直不是很理解