推 patabon:我第一題寫ve^2 @@ 第二題跟你一樣 01/19 13:53
推 frank73:兩題都跟你一樣 01/19 20:19
→ gn123:第一題我是看洪傑筆記的~"~ 所以也不知道正不正確 01/19 23:17
推 patabon:應該是你的寫法才是對的xd 請忽略我的答案 01/20 00:10
→ gn123:好喔! 感謝~ 01/20 17:05
http://ppt.cc/WbDP
第一題應該是 O(E*f) = O(m*f)
想請問第二題,
每個邊(arcs)都加y,而max-flow(min cut capacity)只會受到從sink流出流量影響
所以這題要求at most
--------
想說圖形是不是長這樣: s -------- t 每條都+y , 所以min-cut capacity=f+x*y
--------
...
--------
(有x條arcs從s分出,然後注入t)
以上是自己的想法,想跟大家討論看看,謝謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.227.171.18