[理工] 100交大資演

看板Grad-ProbAsk作者 (PTT領導)時間9年前 (2017/02/03 15:59), 編輯推噓0(0推 0噓 5→)
留言5則, 1人參與, 最新討論串1/3 (看更多)
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
→
02/03 16:46, , 1F
augmenting path應該是指還有流量可以流過去的path
02/03 16:46, 1F
→
02/03 16:46, , 2F
達到max flow應該就沒有augmenting path了
02/03 16:46, 2F
→
02/03 16:48, , 3F
C應該不只O(n)個cut?一個cut可以把點集分成兩堆
02/03 16:48, 3F
→
02/03 16:50, , 4F
直覺上會有[C(n,1)+C(n,2)+C(n,3)+...+C(n,n-1)]/2個
02/03 16:50, 4F
→
02/03 16:50, , 5F
約為O(2^n)個，不知道對不對
02/03 16:50, 5F
‣ 更多 PTTleader 的文章
文章代碼(AID): #1Ob3X7yC (Grad-ProbAsk)
‣ 更多 PTTleader 的文章
文章代碼(AID): #1Ob3X7yC (Grad-ProbAsk)