[理工] [演算法] 最短路徑&最大流量

看板Grad-ProbAsk作者 (bear)時間9年前 (2016/12/02 17:45), 9年前編輯推噓4(4推 0噓 11→)
留言15則, 5人參與, 最新討論串1/2 (看更多)
http://i.imgur.com/jrsHj3H.jpg
我的答案為 ＴＴＦＴＴ 但 (a) (d) (e) 不太確定 (a) 這題不太確定是在問single source還是all pair 如果是single source的話應該可以化成Dijkstra 這樣會比Bellman_Ford快吧 (d) 因為乘上2不會改變原本的大小關係？ (e) 我的直覺選True 但不太確定希望有高手幫忙解惑 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.34.13 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1480671905.A.A04.html ※ 編輯: beargg0305 (223.137.34.13), 12/02/2016 17:45:47 ※ 編輯: beargg0305 (223.137.34.13), 12/02/2016 17:46:24
推
12/02 17:55, , 1F
a要稀疏矩陣 再加上Johnson's algo才比較快
12/02 17:55, 1F
→
12/02 17:57, , 2F
A false reweight 是指johnson algo
12/02 17:57, 2F
→
12/02 17:59, , 3F
但Johnson's algo 時間複雜度是(bellman+ dijkstra)
12/02 17:59, 3F
推
12/02 18:00, , 4F
我看錯了 看成all pair
12/02 18:00, 4F
→
12/02 18:00, , 5F
d對吧 e再想想
12/02 18:00, 5F
→
12/02 18:04, , 6F
E 我今天才剛要看 看有沒有其他人會可以回答@@
12/02 18:04, 6F
→
12/02 18:05, , 7F
感覺看完了也不太會選 囧
12/02 18:05, 7F
→
12/02 19:37, , 8F
我覺得E是對的耶 C都+1應該沒差吧?
12/02 19:37, 8F
推
12/02 20:01, , 9F
E應該是對的喔 因為所有加一之後 切集還是最小切集
12/02 20:01, 9F
→
12/02 20:08, , 10F
我錯惹 要視該切集有幾條邊決定 即使是最小切集
12/02 20:08, 10F
→
12/02 20:08, , 11F
如果他擁有的邊過多 每個邊+1後就可能不是最小切集了
12/02 20:08, 11F
推
12/03 00:52, , 12F
我覺得這題就是要考人懂不懂reweight 為什麼不能
12/03 00:52, 12F
→
12/03 00:52, , 13F
直接用全部的邊統一加上某個值shift的function 來
12/03 00:52, 13F
→
12/03 00:52, , 14F
做，從這個角度下去想，就會知道他DE為什麼這樣出
12/03 00:52, 14F
→
12/03 00:52, , 15F
了
12/03 00:52, 15F
‣ 更多 beargg0305 的文章
文章代碼(AID): #1OGKAXe4 (Grad-ProbAsk)
‣ 更多 beargg0305 的文章
文章代碼(AID): #1OGKAXe4 (Grad-ProbAsk)