[理工] [演算法] 最短路徑&最大流量
作者: beargg0305 (bear) 2016-12-02 17:45:03
我的答案為
ＴＴＦＴＴ
但 (a) (d) (e) 不太確定
(a)
這題不太確定是在問single source還是all pair
如果是single source的話應該可以化成Dijkstra
這樣會比Bellman_Ford快吧
(d)
因為乘上2不會改變原本的大小關係？
(e)
我的直覺選True
但不太確定希望有高手幫忙解惑
作者: hopward (hopward) 2016-12-02 17:55:00
a要稀疏矩陣 再加上Johnson's algo才比較快
作者: ken52011219 (呱) 2016-12-02 17:57:00
A false reweight 是指johnson algo但Johnson's algo 時間複雜度是(bellman+ dijkstra)
作者: hopward (hopward) 2016-12-02 18:00:00
我看錯了 看成all paird對吧 e再想想
作者: ken52011219 (呱) 2016-12-02 18:04:00
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:00
E應該是對的喔 因為所有加一之後 切集還是最小切集我錯惹 要視該切集有幾條邊決定 即使是最小切集如果他擁有的邊過多 每個邊+1後就可能不是最小切集了
作者: windwaker112 (阿茄) 2016-12-03 00:52:00
我覺得這題就是要考人懂不懂reweight 為什麼不能直接用全部的邊統一加上某個值shift的function 來做，從這個角度下去想，就會知道他DE為什麼這樣出了