作者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/cn.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