[理工] 102中央資演 ANANquenchan PTT批踢踢實業坊

[理工] 102中央資演

作者: ANANquenchan (ananquenchana) 2018-12-02 15:16:48

本人對於演算法比較陌生ˊˋ
一開始看到此題的想法是用BFS跑看看
但實際上該怎麼寫不太清楚
想問問各位強人的想法
https://i.imgur.com/tao4nVT.jpg

作者: TEPLUN (mihanami) 2018-12-03 02:26:00

假設加入的是(u,v) 必定行成cycle 先不考慮此邊對原圖的MST從u開始做bfs 紀錄u到v在MST的路徑上最大的邊若最大邊權重比w(u,v)大就替換否則維持原樣

作者: ANANquenchan (ananquenchana) 2018-12-03 17:34:00

可是這樣如果做(u,v)跟最大邊替換，怎麼能保證不會變成disconnected

作者: TEPLUN (mihanami) 2018-12-03 18:48:00

加入那個邊一定行成cycle 這個cycle任意去掉一邊還是聯通圖

作者: ANANquenchan (ananquenchana) 2018-12-04 11:42:00

哦了解了謝謝T大

繼續閱讀

演算法 P26 程式時間複雜度ENGneweu [理工] 離散2-109AttitudeLA Re: [理工] 線代inner product題目Honor1984 [理工] 線代inner product題目leekevinming [理工] os process觀念題alice85319 [理工] 演算法 maximum flow問題paralyzation [理工] [線代] 內積空間公理證明leekevinming [理工] 離散6-65觀念！Aa841018 [理工] 計組 pipelinedecoder [理工] 交大線代HY0869

Contact Us: admin [ a t ] ucptt.com