作者liljimmy (吉米)
看板Grad-ProbAsk
标题[理工] 演算法 Ford-Fulkerson问题
时间Fri Nov 27 13:50:06 2020
https://i.imgur.com/gj3EXz0.jpg
请问这题的B选项，题目说任意边的capacity都是整数，推测选项意思应该是：执行Ford-Fu
lkerson找到一条augmenting path时，不一定要把他补满可以只加任意flow，所以才会有可
能产生小数的flow在边上，不知道这样理解对不对？
https://i.imgur.com/OjFKR2m.jpg
这边想问一下名词””arc””的定义是什麽？
看答案推敲是指minimum cut上所有的边都叫做arc吗？
先谢谢各位高手。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.77.223.227 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1606456208.A.189.html
1F：推 mi981027: 1. 不对 在capacity是整数的情况下用FF找到的一定是整 11/28 00:27
2F：→ mi981027: 数，这在CLRS有个定理 11/28 00:27
3F：推 mi981027: 只是最佳解本来就不一定要是整数，可以稍微画个简单的 11/28 00:32
4F：→ mi981027: 图试试看，立宇的书里应该也有例子 11/28 00:32
5F：→ liljimmy: @mi981027 感谢 那题了解了 11/28 11:13
6F：→ liljimmy: 第二题的arc是什麽意思还是不会QQ 11/28 11:13
7F：推 FRAXIS: arc 就是 edge 11/28 13:27
8F：→ liljimmy: @FRAXIS 那这边他指的minicut s-t中的arcs就是 12/01 11:01
9F：→ liljimmy: 指两个集合之间所连结的边吗？ 12/01 11:01
10F：→ liljimmy: 那这题後面是要我们在上述这些「arcs」上capacity+1这 12/01 11:01
11F：→ liljimmy: 样吗？抱歉还是不太懂 12/01 11:01