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,这不是费用流
|