作者qazwsxedc597 (Deus)
看板Grad-ProbAsk
标题[理工] 演算法ford-Fulkerson 观念
时间Fri Dec 11 05:29:14 2020
https://i.imgur.com/tY5SzNU.jpg
我想问书中说的这种情况如果都是用DFS去找path
最差的情况为什麽会第一次走suvt,第二次却走svut而不会走sut,我知道他要表达的
意思,但是他给的例子我不是很理解,dfs第一次先选u第二次会换成先选v?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.175.99.170 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1607635756.A.F01.html
1F：→ aa871220: 从residual network看 一开始选svut就会只剩一条suvt能12/11 09:34
2F：→ aa871220: 选然後一直循环下去12/11 09:34
3F：推 alex391a: 楼上 没有吧 suvt 过後下一轮还是有sut 可以选12/11 09:40
4F：→ alex391a: 题目没有说用什麽方式取 只是想表达最坏情况而已 没什麽12/11 09:40
5F：→ aa871220: Sor脑袋混沌== 反正他就表达随机选augmenting path是很12/11 10:02
6F：→ aa871220: 烂的方法12/11 10:02
※ 编辑: qazwsxedc597 (223.138.119.2 台湾), 12/11/2020 11:41:21
7F：→ mathtsai: 他想表达的就是如果p选得很烂 你的程式可能会炸掉 12/11 12:34