http://i.imgur.com/jrsHj3H.jpg
我的答案为
ＴＴＦＴＴ
但 (a) (d) (e) 不太确定
(a)
这题不太确定是在问single source还是all pair
如果是single source的话应该可以化成Dijkstra
这样会比Bellman_Ford快吧
(d)
因为乘上2不会改变原本的大小关系？
(e)
我的直觉选True
但不太确定希望有高手帮忙解惑

a要稀疏矩阵 再加上Johnson's algo才比较快

A false reweight 是指johnson algo但Johnson's algo 时间复杂度是(bellman+ dijkstra)

我看错了 看成all paird对吧 e再想想

E 我今天才刚要看 看有没有其他人会可以回答@@

感觉看完了也不太会选 囧

我觉得E是对的耶 C都+1应该没差吧?

E应该是对的喔 因为所有加一之后 切集还是最小切集我错惹 要视该切集有几条边决定 即使是最小切集如果他拥有的边过多 每个边+1后就可能不是最小切集了

我觉得这题就是要考人懂不懂reweight 为什么不能直接用全部的边统一加上某个值shift的function 来做，从这个角度下去想，就会知道他DE为什么这样出了