嘿，这个问题我之前做算法作业的时候也卡过！你想保留某个原有的最小生成树（MST）同时让它变成图中唯一MST的核心，其实是针对性区分目标MST的边和非树边来调整权重，而不是盲目地去重所有边权——之前的方案之所以失效，就是因为没考虑到环里的边权重调整会破坏原MST的最小性。

下面是具体的可行步骤，亲测有效：

• 第一步：先选定你要保留的目标MST T，把图中的边明确分成两类：树边（属于T的边）和非树边（不属于T的边）。
• 第二步：微调树边的权重，保证它们的相对顺序不变，但彼此有微小差异。比如选一个极小的正数ε（比如ε=1e-9，要远小于原图中任意两条不同边的权重差），然后给每条树边e赋予新权重：w'(e) = w(e) + k*ε，这里k是从1开始的递增整数（比如按你遍历树边的顺序依次赋值）。这样做的目的是让树边之间有细微的权重差异，但整体权重总和依然远小于用非树边替换树边的情况。
• 第三步：处理非树边，确保它们永远无法替代树边进入最小生成树。对于每条非树边e'，找到它和T形成的环，找出这个环里权重最大的树边（调整前的权重就行，因为ε极小不影响大小关系），然后设置w'(e') = max_tree_edge_w + ε。这样一来，任何非树边的权重都严格大于它所在环里的最大树边，用它替换树边只会让生成树的总权重变大，自然不会形成新的MST。

为什么这个方法能解决你的问题？ #

你之前尝试让所有边权唯一，但如果随便修改边权，很可能会让原MST里的边权重超过某些非树边，导致原MST不再是最小的。而这个方法的核心是优先保证目标MST的权重优势：

• 树边的微调只是给它们加了极小的增量，不会让树边的总权重超过其他原本不是MST的生成树；
• 非树边的调整直接切断了它们替换树边的可能，彻底消除了其他MST存在的基础。

举个简单例子：假设原图有一个3节点环，三条边权重都是2，你选定其中两条边作为目标MST。给这两条树边分别加ε和2ε，变成2+ε和2+2ε；非树边设置为2+2ε+ε=2+3ε。此时目标MST的总权重是4+3ε，而如果用非树边替换任意一条树边，总权重都会变成4+4ε，比目标MST大，所以唯一的MST就是你选定的那棵。

注意事项 #

• ε的选择要足够小，比如如果原图中任意两条不同边的权重差最小是Δ，那么ε要小于Δ/n（n是图的节点数），这样所有树边的总增量不会超过nε < Δ，不会破坏原有的边权大小关系。

内容的提问来源于stack exchange，提问作者user13608061