→ mathtsai: 知道BFS複雜度就知道啦 01/07 19:57
推 codepo: 令e=(vi , vj), I ≠ j, 每一個點與其他點相連的邊用 adj 01/31 00:18
→ codepo: acent list 表示，則每次在找邊時可能花 O(E) 時間 01/31 00:18
https://imgur.com/l6GOxNP
想請問第25題的部分，為什麼第二個 while 每次都要執行 O(|E|) 次的 BFS?
是因為 augmenting path 最多就是點的排序，所以有O(|V|^2 ) = O(|E|)嗎?
謝謝大家~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.123.81 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1673085661.A.CE1.html