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

出一道题,大家玩玩,关于图的

  •  
  •   zealot0630 · 2019-06-16 13:44:48 +08:00 · 3021 次点击
    这是一个创建于 1748 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题

    给定一张无向图,求这张图第一个节点到最后一个节点的最大带宽。

    解释

    给定一张有 N 个节点的无向图 G,G[X,Y]表示节点 X 与节点 Y 之间的带宽,求节点 1 到节点 N 之间的最大带宽。

    流量可以通过任意节点中转,比如 1 -> 2 -> 3,

    举例

    比如这张有 4 个节点的图:

    [1]--6--[2]
     | \     |
     |  \    |
     8   7  100
     |    \  |
     |     \ |
    [3]--6--[4]
    

    节点 1 到节点 4 的最大带宽为 19

    14 条回复    2019-06-17 09:53:19 +08:00
    thedog
        1
    thedog  
       2019-06-16 13:54:19 +08:00
    所以是遍历所有路径,然后对所有路径的最大流量加和?
    BiteTheDust
        2
    BiteTheDust  
       2019-06-16 13:54:54 +08:00
    有人能告诉我这个和最大流有什么区别吗?
    kppwp
        3
    kppwp  
       2019-06-16 14:12:37 +08:00 via iPhone
    max flow
    jiangdong42
        4
    jiangdong42  
       2019-06-16 14:54:57 +08:00   ❤️ 1
    @thedog 对所有路径的最小流量加和
    zqqian
        5
    zqqian  
       2019-06-16 14:58:34 +08:00 via iPhone
    网络流模板
    直接用 dinic 算法跑就可以
    RicardoY
        6
    RicardoY  
       2019-06-16 15:11:09 +08:00 via Android
    这不就是最大流吗..
    111qqz
        7
    111qqz  
       2019-06-16 15:24:37 +08:00 via Android
    模板题没什么玩的意义吧……
    jc89898
        8
    jc89898  
       2019-06-16 15:47:46 +08:00
    @jiangdong42 不是吧,我记得算法还有用负流量的
    will0404
        9
    will0404  
       2019-06-16 15:54:56 +08:00
    狄克斯特拉算法变种
    will0404
        10
    will0404  
       2019-06-16 15:56:45 +08:00
    补充下,如果有负权重(负流量)则狄克斯特拉算法不适用
    jiejiss
        11
    jiejiss  
       2019-06-16 18:53:50 +08:00
    这就是个最大流吧……
    就算不知道最大流,手写一个路径遍历不到十分钟就写完了
    brainfxxk
        12
    brainfxxk  
       2019-06-16 19:08:10 +08:00
    裸的最大流 建图都不用建 有什么好玩的?
    snw
        13
    snw  
       2019-06-16 20:45:48 +08:00 via Android
    如果是节点 2 到节点 3 呢?如果直接遍历相加的话是不是会重复计算?
    im0qianqian
        14
    im0qianqian  
       2019-06-17 09:53:19 +08:00
    @BiteTheDust 没有区别,哈哈哈
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2849 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 13:41 · PVG 21:41 · LAX 06:41 · JFK 09:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.