作者PTTleader (PTT領導)
看板Grad-ProbAsk
標題[理工] 100交大資演
時間Fri Feb 3 15:59:00 2017
http://imgur.com/a/JNpGl
想問57(A)選項是甚麼意思阿 為甚麼對
augmenting path 怎麼會沒有
想問什麼是augmenting path
(C)的話是錯在哪裡?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.224.44.120
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486108743.A.F0C.html
→ yupog2003: augmenting path應該是指還有流量可以流過去的path 02/03 16:46
→ yupog2003: 達到max flow應該就沒有augmenting path了 02/03 16:46
→ yupog2003: C應該不只O(n)個cut?一個cut可以把點集分成兩堆 02/03 16:48
→ yupog2003: 直覺上會有[C(n,1)+C(n,2)+C(n,3)+...+C(n,n-1)]/2個 02/03 16:50
→ yupog2003: 約為O(2^n)個，不知道對不對 02/03 16:50