作者Aa841018 (andrew)
看板Grad-ProbAsk
標題[理工] 交大資演數題！
時間Tue Jan 7 11:34:49 2020
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://webptt.com/m.aspx?n=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
1F：→ zuchang: 我在猜108 26 E integral是完整 不是整數的意思 就說得通 01/07 11:43
2F：推 zuchang: 順便問一下25複雜度怎麼看的 我寫lgC(V+E) 01/07 11:45
3F：推 mistel: 是整數沒錯，但最大流你可以取分數的邊 有個定理是說若邊 01/07 11:47
4F：→ mistel: 為整數，則「使用」ford fulkerson出來的結果所有邊皆為 01/07 11:47
5F：→ mistel: 整數 但不代表最大流不可以取分數 01/07 11:47
6F：推 mistel: 57答案不是D嗎？你不是都把E劃掉了？ 01/07 11:50
7F：→ Aa841018: 但取分數不就代表不是max flow嗎？因為怎樣取都不可能超 01/07 11:51
8F：→ Aa841018: 過capacity，那既然capacity是整數，那取分數唯一可能就 01/07 11:51
9F：→ Aa841018: 是比capacity少取一點，但這樣不是max flow吧？ 01/07 11:51
11F：→ Aa841018: 57.是選錯的，但我覺得某些狀況下E也會錯，但答案只有D 01/07 11:53
12F：推 mistel: 不會啊 只是反例比較難想 01/07 11:57
14F：→ mistel: 看了一下55.，他的compute是指拿bellman ford的結果算出 01/07 11:59
15F：→ mistel: 每個點的新值？這樣就是O(V) 01/07 11:59
16F：→ Aa841018: 感謝m大提供反例！ 01/07 12:00
17F：推 FRAXIS: 存在有一個 maximum flow 是整數 但是可以有其他的 01/07 12:02
18F：→ FRAXIS: maximum flow 不是整數 01/07 12:02
19F：→ Aa841018: 關於57還是有些不明白，即使bellman算出s到各點的Shorte 01/07 12:06
20F：→ Aa841018: st path，但在reweight時仍是在G中找所有edge，那如果ed 01/07 12:06
21F：→ Aa841018: ge數多，仍然有可能會超出O(V)吧？ 01/07 12:06
22F：→ zuchang: compute只是在每個點上面標出bellman求出來的s到各點距離 01/07 12:17
23F：推 gash55025502: 我記得57的G’只是多加一個起點並連向其他邊而已 你 01/07 12:24
24F：→ gash55025502: 可以回去看一下程式碼 01/07 12:24
25F：推 zuchang: 就是把h0-hv填進去而已 01/07 12:25
26F：→ Aa841018: 懂了，謝謝各位 01/07 12:35