V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
letianqiu
V2EX  ›  程序员

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

  •  
  •   letianqiu · 2018-05-07 18:38:51 +08:00 · 2184 次点击
    这是一个创建于 2371 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给定一个 Network Flow 的 Graph,source,sink 以及 Graph 中任意两个 vertex: u 和 v。现在要求找出一个 cut,使得 u 和 source 属于同一个 set,v 和 sink 属于同一个 set,并且这个 cut 的 capacity 要求最小。
    7 条回复    2018-05-07 20:01:23 +08:00
    fancy20
        1
    fancy20  
       2018-05-07 18:54:15 +08:00
    最大流等于最小割,dinic, isap ?
    kilnyy
        2
    kilnyy  
       2018-05-07 19:14:29 +08:00
    建一个 vertex 超级源 和 source 与 u 连接,建一个 vertex 超级汇,和 sink 与 v 连接。这四条边 cost 设置为无穷大。然后正常求超级源汇之间的最小割。
    letianqiu
        3
    letianqiu  
    OP
       2018-05-07 19:38:10 +08:00
    @kilnyy 能解释一下这么做的原因吗?
    myk502
        4
    myk502  
       2018-05-07 19:50:49 +08:00   ❤️ 1
    蒟蒻试着解释一下。。
    首先,最小割就是最大流的对偶问题,并且割边(连接两个割集的边)必须跑满
    既然超级源到 source 超级源到 u 容量都为无穷大,那么肯定不是割边,那么 source 和 u 必定都属于 S 割点集。
    同理,balabalala
    所以 u v 会属于不同的两个割集
    然后显然,添加的 4 条边不会影响最大流的流量(其实是我不会证明。。)
    所以。。就好了
    myk502
        5
    myk502  
       2018-05-07 19:51:15 +08:00
    不是 cost, 是 capacity,这不是费用流
    myk502
        6
    myk502  
       2018-05-07 19:58:45 +08:00
    @letianqiu 老兄看你最近发的都是这种题,是不是在上算法课啊。最大流最小割建议看胡伯涛的 noi 冬令营论文。
    letianqiu
        7
    letianqiu  
    OP
       2018-05-07 20:01:23 +08:00
    @myk502 没错啊。最大流一直不是很理解
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2844 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 14:31 · PVG 22:31 · LAX 07:31 · JFK 10:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.