[理工] 102中央資演

[ANANquenchan (ananquenchana)]

本人對於演算法比較陌生ˊˋ
一開始看到此題的想法是用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
推 TEPLUN: 假設加入的是(u,v) 必定行成cycle 先不考慮此邊 對原圖的M
→ TEPLUN: ST從u開始做bfs 紀錄u到v在MST的路徑上最大的邊 若最大邊
→ TEPLUN: 權重比w(u,v)大 就替換 否則維持原樣
→ ANANquenchan: 可是這樣如果做(u,v)跟最大邊替換，怎麼能保證不會
→ ANANquenchan: 變成disconnected
推 TEPLUN: 加入那個邊一定行成cycle 這個cycle任意去掉一邊還是聯通
→ TEPLUN: 圖
→ ANANquenchan: 哦了解了謝謝T大