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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1985 天前的主题，其中的信息可能已经有所发展或是发生改变。

问题

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

解释

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

2019-06-16 13:54:19 +08:00

所以是遍历所有路径，然后对所有路径的最大流量加和？

BiteTheDust

2019-06-16 13:54:54 +08:00

有人能告诉我这个和最大流有什么区别吗？

kppwp

2019-06-16 14:12:37 +08:00 via iPhone

max flow

jiangdong42

2019-06-16 14:54:57 +08:00

@thedog 对所有路径的最小流量加和

zqqian

2019-06-16 14:58:34 +08:00 via iPhone

网络流模板
直接用 dinic 算法跑就可以

RicardoY

2019-06-16 15:11:09 +08:00 via Android

这不就是最大流吗..

111qqz

2019-06-16 15:24:37 +08:00 via Android

模板题没什么玩的意义吧……

jc89898

2019-06-16 15:47:46 +08:00

@jiangdong42 不是吧，我记得算法还有用负流量的

will0404

2019-06-16 15:54:56 +08:00

狄克斯特拉算法变种

will0404

2019-06-16 15:56:45 +08:00

补充下，如果有负权重（负流量）则狄克斯特拉算法不适用

jiejiss

2019-06-16 18:53:50 +08:00

这就是个最大流吧……
就算不知道最大流，手写一个路径遍历不到十分钟就写完了

brainfxxk

2019-06-16 19:08:10 +08:00

裸的最大流建图都不用建有什么好玩的？

snw

2019-06-16 20:45:48 +08:00 via Android

如果是节点 2 到节点 3 呢？如果直接遍历相加的话是不是会重复计算？

im0qianqian

2019-06-17 09:53:19 +08:00

@BiteTheDust 没有区别，哈哈哈