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

2019 年 6 月 16 日
 zealot0630

问题

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

解释

给定一张有 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

4475 次点击
所在节点    程序员
14 条回复
thedog
2019 年 6 月 16 日
所以是遍历所有路径，然后对所有路径的最大流量加和？
BiteTheDust
2019 年 6 月 16 日
有人能告诉我这个和最大流有什么区别吗？
kppwp
2019 年 6 月 16 日
max flow
jiangdong42
2019 年 6 月 16 日
@thedog 对所有路径的最小流量加和
zqqian
2019 年 6 月 16 日
网络流模板
直接用 dinic 算法跑就可以
RicardoY
2019 年 6 月 16 日
这不就是最大流吗..
midasplus
2019 年 6 月 16 日
模板题没什么玩的意义吧……
jc89898
2019 年 6 月 16 日
@jiangdong42 不是吧，我记得算法还有用负流量的
will0404
2019 年 6 月 16 日
狄克斯特拉算法变种
will0404
2019 年 6 月 16 日
补充下，如果有负权重（负流量）则狄克斯特拉算法不适用
jiejiss
2019 年 6 月 16 日
这就是个最大流吧……
就算不知道最大流，手写一个路径遍历不到十分钟就写完了
brainfxxk
2019 年 6 月 16 日
裸的最大流 建图都不用建 有什么好玩的？
snw
2019 年 6 月 16 日
如果是节点 2 到节点 3 呢？如果直接遍历相加的话是不是会重复计算？
im0qianqian
2019 年 6 月 17 日
@BiteTheDust 没有区别，哈哈哈

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/574428

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX