作者wilson50101 (我觉得我还不错啊)
看板Grad-ProbAsk
标题[理工] 演算法MST第35题
时间Tue Oct 16 21:25:57 2018
https://i.imgur.com/bMW8Tlv.jpg
https://i.imgur.com/IcoZ3Uq.jpg
关於这题我有其他想法不知道可不可行
1.就先把edge e加入G
因为MST:T是G的spanning tree
所以加入edge e 必形成cycle
2.针对cycle上的边找出weight最大者踢掉
沿着cycle比较找出最大者花费顶多O(n)(因为顶多形成n个点n个边的大cycle)
3.新的Tree即为新的MST
正确性的部分:
要踢掉的一定是cycle内的边
若踢不在cycle内的边不会是tree
所以只要能保证踢掉cycle内最大的边
即能保证新tree即为MST
不知道我这样子想法有没有问题
-----
Sent from JPTT on my iPad
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.170.117.9
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1539696359.A.82E.html
1F：推 FRAXIS: 你这方法跟解答上的有何不同 10/17 11:10
2F：→ wilson50101: 後来想想这做法跟解答有点大同小异？ 10/17 11:14
3F：→ wilson50101: 解答是用BFS找出path然後加上边形成cycle 10/17 11:14
4F：→ wilson50101: 我的是直接用离散的想法讲他会形成cycle这样 10/17 11:14