假设给定图G的最小生成树T(其中n
顶点和m个边)和一个新边e =(u，v)的权重w，我们将其添加到G。
给出一个有效的算法来找到图G + e的最小生成树。
您的算法应在O(n)时间内运行才能获得全额功劳。
(c)从Skiena手册
从u或v启动Prim或Kruskal alg，直到到达给定的生成树路径的片段？似乎新的生成树从一个新的边缘不会发生太大变化。
最佳答案
确定G中新边的端点之间的路径。如果该路径中最大边的长度大于新边的长度，请用新边替换它。这需要O(N)时间。
资料来源:Trail Maintenance IOI 2003