这是一个创建于 2426 天前的主题，其中的信息可能已经有所发展或是发生改变。
给定一个 Network Flow 的 Graph，source，sink 以及 Graph 中任意两个 vertex: u 和 v。现在要求找出一个 cut，使得 u 和 source 属于同一个 set，v 和 sink 属于同一个 set，并且这个 cut 的 capacity 要求最小。
 |
1
fancy20 2018-05-07 18:54:15 +08:00
最大流等于最小割，dinic, isap ？
|
 |
2
kilnyy 2018-05-07 19:14:29 +08:00
建一个 vertex 超级源 和 source 与 u 连接，建一个 vertex 超级汇，和 sink 与 v 连接。这四条边 cost 设置为无穷大。然后正常求超级源汇之间的最小割。
|
 |
4
myk502 2018-05-07 19:50:49 +08:00  1
蒟蒻试着解释一下。。
首先，最小割就是最大流的对偶问题，并且割边（连接两个割集的边）必须跑满 既然超级源到 source 超级源到 u 容量都为无穷大，那么肯定不是割边，那么 source 和 u 必定都属于 S 割点集。 同理，balabalala 所以 u v 会属于不同的两个割集 然后显然，添加的 4 条边不会影响最大流的流量（其实是我不会证明。。） 所以。。就好了 |
|
5
myk502 2018-05-07 19:51:15 +08:00
不是 cost， 是 capacity，这不是费用流
|
Select Language