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都是整數，怎樣都不可能是非整數吧？請問我哪裡有想錯嗎？

我在猜108 26 E integral是完整 不是整數的意思 就說得通順便問一下25複雜度怎麼看的 我寫lgC(V+E)

是整數沒錯，但最大流你可以取分數的邊 有個定理是說若邊為整數，則「使用」ford fulkerson出來的結果所有邊皆為整數 但不代表最大流不可以取分數57答案不是D嗎？你不是都把E劃掉了？

但取分數不就代表不是max flow嗎？因為怎樣取都不可能超過capacity，那既然capacity是整數，那取分數唯一可能就是比capacity少取一點，但這樣不是max flow吧？

補一下完整題目https://i.imgur.com/xdhH3JU.jpg

57.是選錯的，但我覺得某些狀況下E也會錯，但答案只有D

不會啊 只是反例比較難想https://i.imgur.com/86wzad1.jpg看了一下55.，他的compute是指拿bellman ford的結果算出每個點的新值？這樣就是O(V)

感謝m大提供反例！

存在有一個 maximum flow 是整數 但是可以有其他的maximum flow 不是整數

關於57還是有些不明白，即使bellman算出s到各點的Shortest path，但在reweight時仍是在G中找所有edge，那如果edge數多，仍然有可能會超出O(V)吧？

compute只是在每個點上面標出bellman求出來的s到各點距離

我記得57的G’只是多加一個起點並連向其他邊而已 你可以回去看一下程式碼

就是把h0-hv填進去而已

懂了，謝謝各位