http://i.imgur.com/jrsHj3H.jpg
我的答案为
ＴＴＦＴＴ
但 (a) (d) (e) 不太确定
(a)
这题不太确定是在问single source还是all pair
如果是single source的话应该可以化成Dijkstra
这样会比Bellman_Ford快吧
(d)
因为乘上2不会改变原本的大小关系？
(e)
我的直觉选True
但不太确定希望有高手帮忙解惑
作者:
hopward (hopward)
2016-12-02 17:55:00a要稀疏矩阵 再加上Johnson's algo才比较快
A false reweight 是指johnson algo但Johnson's algo 时间复杂度是(bellman+ dijkstra)
作者:
hopward (hopward)
2016-12-02 18:00:00我看错了 看成all paird对吧 e再想想
作者:
hopward (hopward)
2016-12-02 18:05:00感觉看完了也不太会选 囧
作者:
histman (嘿嘿嘿)
2016-12-02 19:37:00我觉得E是对的耶 C都+1应该没差吧?
作者:
kyuudonut (善良è€ç™¾å§“)
2016-12-02 20:01:00E应该是对的喔 因为所有加一之后 切集还是最小切集我错惹 要视该切集有几条边决定 即使是最小切集如果他拥有的边过多 每个边+1后就可能不是最小切集了
我觉得这题就是要考人懂不懂reweight 为什么不能直接用全部的边统一加上某个值shift的function 来做，从这个角度下去想，就会知道他DE为什么这样出了