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