[理工] 102中央資演

看板Grad-ProbAsk作者 (ananquenchana)時間7年前 (2018/12/02 15:16), 編輯推噓2(2推 0噓 6→)
留言8則, 2人參與, 7年前最新討論串1/1
本人對於演算法比較陌生ˊˋ 一開始看到此題的想法是用BFS跑看看 但實際上該怎麼寫不太清楚 想問問各位強人的想法 https://i.imgur.com/tao4nVT.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.82.209.154 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543735010.A.056.html
推
12/03 02:26, 7年前 , 1F
假設加入的是(u,v) 必定行成cycle 先不考慮此邊 對原圖的M
12/03 02:26, 1F
→
12/03 02:26, 7年前 , 2F
ST從u開始做bfs 紀錄u到v在MST的路徑上最大的邊 若最大邊
12/03 02:26, 2F
→
12/03 02:26, 7年前 , 3F
權重比w(u,v)大 就替換 否則維持原樣
12/03 02:26, 3F
→
12/03 17:34, 7年前 , 4F
可是這樣如果做(u,v)跟最大邊替換，怎麼能保證不會
12/03 17:34, 4F
→
12/03 17:34, 7年前 , 5F
變成disconnected
12/03 17:34, 5F
推
12/03 18:48, 7年前 , 6F
加入那個邊一定行成cycle 這個cycle任意去掉一邊還是聯通
12/03 18:48, 6F
→
12/03 18:48, 7年前 , 7F
圖
12/03 18:48, 7F
→
12/04 11:42, 7年前 , 8F
哦了解了謝謝T大
12/04 11:42, 8F
‣ 更多 ANANquenchan 的文章
文章代碼(AID): #1S0uRY1M (Grad-ProbAsk)