[理工] 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