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填进去而已

懂了，谢谢各位