这是一个创建于 2403 天前的主题，其中的信息可能已经有所发展或是发生改变。
问题
给定一张无向图，求这张图第一个节点到最后一个节点的最大带宽。
解释
给定一张有 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 年 6 月 16 日
所以是遍历所有路径，然后对所有路径的最大流量加和？
|
 |
2
BiteTheDust 2019 年 6 月 16 日
有人能告诉我这个和最大流有什么区别吗？
|
 |
3
kppwp 2019 年 6 月 16 日 via iPhone
max flow
|
 |
4
jiangdong42 2019 年 6 月 16 日  1
@thedog 对所有路径的最小流量加和
|
 |
5
zqqian 2019 年 6 月 16 日 via iPhone
网络流模板
直接用 dinic 算法跑就可以 |
 |
6
RicardoY 2019 年 6 月 16 日 via Android
这不就是最大流吗..
|
 |
7
midasplus 2019 年 6 月 16 日 via Android
模板题没什么玩的意义吧……
|
 |
8
jc89898 2019 年 6 月 16 日
@jiangdong42 不是吧，我记得算法还有用负流量的
|
 |
9
will0404 2019 年 6 月 16 日
狄克斯特拉算法变种
|
|
10
will0404 2019 年 6 月 16 日
补充下，如果有负权重（负流量）则狄克斯特拉算法不适用
|
 |
11
jiejiss 2019 年 6 月 16 日
这就是个最大流吧……
就算不知道最大流，手写一个路径遍历不到十分钟就写完了 |
 |
12
brainfxxk 2019 年 6 月 16 日
裸的最大流 建图都不用建 有什么好玩的？
|
 |
13
snw 2019 年 6 月 16 日 via Android
如果是节点 2 到节点 3 呢？如果直接遍历相加的话是不是会重复计算？
|
 |
14
im0qianqian 2019 年 6 月 17 日
@BiteTheDust 没有区别，哈哈哈
|
Select Language