知识卡片
顶点容量通过拆点变成边容量
把顶点v拆为v_in和v_out,并添加容量为k(v)的边 v_in→v_out;原入边连接v_in,原出边从v_out出发并保留各自原容量。根据问题定义决定源、汇是否也受顶点容量约束。
无向边的建模需明确是否共享双向容量;在普通单物资净流问题中可用两条反向容量边并消去互相抵消的流,但不能把这一转换无条件推广到多物资共享容量。
240的03394通过仓库入点和出点之间的边表达仓库吞吐上限及单位处理成本;源供给与汇需求边则表达上下限。规约后仍需核验总需求是否全部满足,不能只检查求解器返回任意非负流。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 顶点容量通过拆点变成边容量
- · 解决方案
原书出处 · 2 处
- · 查看原书依据
顶点容量 如果流网络中的每个顶点v都有一个最大容量k(v)将会怎么样呢?构建一个修改过的图G'。对于网络中的每个顶点v,构建两个顶点v'和v"。并且创建一条边(v",v'),这条边的容量是k(v)。在图G中创建一条容量为c(x,v)的边(x,v),对应原始图G中的容量为c(x,v)的每条边(x,v"
- · 查看原书依据
转运问题转换成最小开销流问题(如图8-8所示),构造了这样一个图G=(V,E): V共有n+m+2*w+2个顶点 每个供应站si被映射成一个顶点i,每个仓库wk映射成两个顶点,m+2*k-1和m+2*k。每个需求站tj映射成顶点1+m+2*w+j。然后创建一个新的源点src(标记为0)和新的汇点tg
参考来源
- 位置:《算法技术手册》第8章《相关算法》(spine1633;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1596.html;u232-ch08-005)。
- 结论依据:232全文实读;保留原边容量修正正文转换。
- 原始内容:顶点容量 如果流网络中的每个顶点v都有一个最大容量k(v)将会怎么样呢?构建一个修改过的图G'。对于网络中的每个顶点v,构建两个顶点v'和v"。并且创建一条边(v",v'),这条边的容量是k(v)。在图G中创建一条容量为c(x,v)的边(x,v),对应原始图G中的容量为c(x,v)的每条边(x,v"
- 位置:《算法技术手册》第8章《解决方案》(spine1639;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1602.html;u240-ch08-005)。
- 结论依据:240的03394通过仓库入点和出点之间的边表达仓库吞吐上限及单位处理成本;源供给与汇需求边则表达上下限。规约后仍需核验总需求是否全部满足,不能只检查求解器返回任意非负流。
- 原始内容:转运问题转换成最小开销流问题(如图8-8所示),构造了这样一个图G=(V,E): V共有n+m+2*w+2个顶点 每个供应站si被映射成一个顶点i,每个仓库wk映射成两个顶点,m+2*k-1和m+2*k。每个需求站tj映射成顶点1+m+2*w+j。然后创建一个新的源点src(标记为0)和新的汇点tg