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

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

  •  
  •   zealot0630 · 174 天前 · 2137 次点击
    这是一个创建于 174 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题

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

    解释

    给定一张有 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
        1
    thedog   174 天前
    所以是遍历所有路径,然后对所有路径的最大流量加和?
        2
    BiteTheDust   174 天前
    有人能告诉我这个和最大流有什么区别吗?
        3
    kppwp   174 天前 via iPhone
    max flow
        4
    jiangdong42   174 天前   ♥ 1
    @thedog 对所有路径的最小流量加和
        5
    zqqian   174 天前 via iPhone
    网络流模板
    直接用 dinic 算法跑就可以
        6
    RicardoY   174 天前 via Android
    这不就是最大流吗..
        7
    111qqz   174 天前 via Android
    模板题没什么玩的意义吧……
        8
    jc89898   174 天前
    @jiangdong42 不是吧,我记得算法还有用负流量的
        9
    will0404   174 天前
    狄克斯特拉算法变种
        10
    will0404   174 天前
    补充下,如果有负权重(负流量)则狄克斯特拉算法不适用
        11
    jiejiss   173 天前
    这就是个最大流吧……
    就算不知道最大流,手写一个路径遍历不到十分钟就写完了
        12
    brainfxxk   173 天前
    裸的最大流 建图都不用建 有什么好玩的?
        13
    snw   173 天前 via Android
    如果是节点 2 到节点 3 呢?如果直接遍历相加的话是不是会重复计算?
        14
    im0qianqian   173 天前
    @BiteTheDust 没有区别,哈哈哈
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2430 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 28ms · UTC 08:58 · PVG 16:58 · LAX 00:58 · JFK 03:58
    ♥ Do have faith in what you're doing.