[理工] 交大資演數題！

看板Grad-ProbAsk作者 (andrew)時間6年前 (2020/01/07 11:34), 6年前編輯推噓7(7推 0噓 19→)
留言26則, 5人參與, 6年前最新討論串1/1
https://i.imgur.com/8site4C.jpg
https://i.imgur.com/qAxOxjo.jpg
上頁其實還有個部分程式碼，只是沒有很重要就不拍了 請問，57（E)，G'和G的差別就差在edge經過reweight 從上面reweight部分看出，是針對每個edge，而且edge num最多可等同vertex num平方， 那(E)選項如果不巧碰到edge num很多的狀況，reweight的時間應該會超越O(|V|)吧？ 但這個選項是對的…… https://i.imgur.com/Oj1GMwv.jpg
https://i.imgur.com/3AMV2XA.jpg
請問26(E) 雖然可以選擇非整數，但max flow肯定要將某些edge的水管賽滿，然後每個edge的capaci ty都是整數，怎樣都不可能是非整數吧？請問我哪裡有想錯嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.44.225 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578368091.A.723.html ※ 編輯: Aa841018 (39.10.44.225 臺灣), 01/07/2020 11:35:27 ※ 編輯: Aa841018 (39.10.44.225 臺灣), 01/07/2020 11:35:50
→
01/07 11:43, 6年前 , 1F
我在猜108 26 E integral是完整 不是整數的意思 就說得通
01/07 11:43, 1F
推
01/07 11:45, 6年前 , 2F
順便問一下25複雜度怎麼看的 我寫lgC(V+E)
01/07 11:45, 2F
推
01/07 11:47, 6年前 , 3F
是整數沒錯，但最大流你可以取分數的邊 有個定理是說若邊
01/07 11:47, 3F
→
01/07 11:47, 6年前 , 4F
為整數，則「使用」ford fulkerson出來的結果所有邊皆為
01/07 11:47, 4F
→
01/07 11:47, 6年前 , 5F
整數 但不代表最大流不可以取分數
01/07 11:47, 5F
推
01/07 11:50, 6年前 , 6F
57答案不是D嗎？你不是都把E劃掉了？
01/07 11:50, 6F
→
01/07 11:51, 6年前 , 7F
但取分數不就代表不是max flow嗎？因為怎樣取都不可能超
01/07 11:51, 7F
→
01/07 11:51, 6年前 , 8F
過capacity，那既然capacity是整數，那取分數唯一可能就
01/07 11:51, 8F
→
01/07 11:51, 6年前 , 9F
是比capacity少取一點，但這樣不是max flow吧？
01/07 11:51, 9F
→
01/07 11:51, 6年前 , 10F
補一下完整題目https://i.imgur.com/xdhH3JU.jpg
01/07 11:51, 10F
→
01/07 11:53, 6年前 , 11F
57.是選錯的，但我覺得某些狀況下E也會錯，但答案只有D
01/07 11:53, 11F
推
01/07 11:57, 6年前 , 12F
不會啊 只是反例比較難想
01/07 11:57, 12F
→
01/07 11:57, 6年前 , 13F
01/07 11:57, 13F
→
01/07 11:59, 6年前 , 14F
看了一下55.，他的compute是指拿bellman ford的結果算出
01/07 11:59, 14F
→
01/07 11:59, 6年前 , 15F
每個點的新值？這樣就是O(V)
01/07 11:59, 15F
→
01/07 12:00, 6年前 , 16F
感謝m大提供反例！
01/07 12:00, 16F
推
01/07 12:02, 6年前 , 17F
存在有一個 maximum flow 是整數 但是可以有其他的
01/07 12:02, 17F
→
01/07 12:02, 6年前 , 18F
maximum flow 不是整數
01/07 12:02, 18F
→
01/07 12:06, 6年前 , 19F
關於57還是有些不明白，即使bellman算出s到各點的Shorte
01/07 12:06, 19F
→
01/07 12:06, 6年前 , 20F
st path，但在reweight時仍是在G中找所有edge，那如果ed
01/07 12:06, 20F
→
01/07 12:06, 6年前 , 21F
ge數多，仍然有可能會超出O(V)吧？
01/07 12:06, 21F
→
01/07 12:17, 6年前 , 22F
compute只是在每個點上面標出bellman求出來的s到各點距離
01/07 12:17, 22F
推
01/07 12:24, 6年前 , 23F
我記得57的G’只是多加一個起點並連向其他邊而已 你
01/07 12:24, 23F
→
01/07 12:24, 6年前 , 24F
可以回去看一下程式碼
01/07 12:24, 24F
推
01/07 12:25, 6年前 , 25F
就是把h0-hv填進去而已
01/07 12:25, 25F
→
01/07 12:35, 6年前 , 26F
懂了，謝謝各位
01/07 12:35, 26F
‣ 更多 Aa841018 的文章
文章代碼(AID): #1U4_nRSZ (Grad-ProbAsk)