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
不知道我这样子想法有没有问题