作者kyh436 (你快看)
看板Grad-ProbAsk
标题[理工] 108 交大资演 题组 12
时间Sat Jan 7 18:00:59 2023
https://imgur.com/l6GOxNP
想请问第25题的部分，为什麽第二个 while 每次都要执行 O(|E|) 次的 BFS?
是因为 augmenting path 最多就是点的排序，所以有O(|V|^2 ) = O(|E|)吗?
谢谢大家~
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.123.81 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1673085661.A.CE1.html
1F：→ mathtsai: 知道BFS复杂度就知道啦 01/07 19:57
2F：推 codepo: 令e=(vi , vj), I ≠ j, 每一个点与其他点相连的边用 adj 01/31 00:18
3F：→ codepo: acent list 表示，则每次在找边时可能花 O(E) 时间 01/31 00:18