[理工] 交大資演數題！

[Aa841018 (andrew)]

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
→ zuchang: 我在猜108 26 E integral是完整 不是整數的意思 就說得通
推 zuchang: 順便問一下25複雜度怎麼看的 我寫lgC(V+E)
推 mistel: 是整數沒錯，但最大流你可以取分數的邊 有個定理是說若邊
→ mistel: 為整數，則「使用」ford fulkerson出來的結果所有邊皆為
→ mistel: 整數 但不代表最大流不可以取分數
推 mistel: 57答案不是D嗎？你不是都把E劃掉了？
→ Aa841018: 但取分數不就代表不是max flow嗎？因為怎樣取都不可能超
→ Aa841018: 過capacity，那既然capacity是整數，那取分數唯一可能就
→ Aa841018: 是比capacity少取一點，但這樣不是max flow吧？
→ zuchang: 補一下完整題目https://i.imgur.com/xdhH3JU.jpg
→ Aa841018: 57.是選錯的，但我覺得某些狀況下E也會錯，但答案只有D
推 mistel: 不會啊 只是反例比較難想
→ mistel: https://i.imgur.com/86wzad1.jpg
→ mistel: 看了一下55.，他的compute是指拿bellman ford的結果算出
→ mistel: 每個點的新值？這樣就是O(V)
→ Aa841018: 感謝m大提供反例！
推 FRAXIS: 存在有一個 maximum flow 是整數  但是可以有其他的
→ FRAXIS: maximum flow 不是整數
→ Aa841018: 關於57還是有些不明白，即使bellman算出s到各點的Shorte
→ Aa841018: st path，但在reweight時仍是在G中找所有edge，那如果ed
→ Aa841018: ge數多，仍然有可能會超出O(V)吧？
→ zuchang: compute只是在每個點上面標出bellman求出來的s到各點距離
推 gash55025502: 我記得57的G’只是多加一個起點並連向其他邊而已 你
→ gash55025502: 可以回去看一下程式碼
推 zuchang: 就是把h0-hv填進去而已
→ Aa841018: 懂了，謝謝各位