给定一张无向图,求这张图第一个节点到最后一个节点的最大带宽。
给定一张有 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
1
thedog 2019-06-16 13:54:19 +08:00
所以是遍历所有路径,然后对所有路径的最大流量加和?
|
2
BiteTheDust 2019-06-16 13:54:54 +08:00
有人能告诉我这个和最大流有什么区别吗?
|
3
kppwp 2019-06-16 14:12:37 +08:00 via iPhone
max flow
|
4
jiangdong42 2019-06-16 14:54:57 +08:00 1
@thedog 对所有路径的最小流量加和
|
5
zqqian 2019-06-16 14:58:34 +08:00 via iPhone
网络流模板
直接用 dinic 算法跑就可以 |
6
RicardoY 2019-06-16 15:11:09 +08:00 via Android
这不就是最大流吗..
|
7
111qqz 2019-06-16 15:24:37 +08:00 via Android
模板题没什么玩的意义吧……
|
8
jc89898 2019-06-16 15:47:46 +08:00
@jiangdong42 不是吧,我记得算法还有用负流量的
|
9
will0404 2019-06-16 15:54:56 +08:00
狄克斯特拉算法变种
|
10
will0404 2019-06-16 15:56:45 +08:00
补充下,如果有负权重(负流量)则狄克斯特拉算法不适用
|
11
jiejiss 2019-06-16 18:53:50 +08:00
这就是个最大流吧……
就算不知道最大流,手写一个路径遍历不到十分钟就写完了 |
12
brainfxxk 2019-06-16 19:08:10 +08:00
裸的最大流 建图都不用建 有什么好玩的?
|
13
snw 2019-06-16 20:45:48 +08:00 via Android
如果是节点 2 到节点 3 呢?如果直接遍历相加的话是不是会重复计算?
|
14
im0qianqian 2019-06-17 09:53:19 +08:00
@BiteTheDust 没有区别,哈哈哈
|