作者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/cn.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