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為什麼這樣出了