关于最小生成树的一道题。。感觉不难。但是想不出来。。
已知set S是一个graph G的minimum spanning tree的edge set, 现在修改了G中的任意一条边的cost（不一定在S中），如何在不重新运行算法的情况下以O(M)（M是总遍数）求得新的新的minimum spanning tree 的edge set？
设计并证明该算法的正确性。。


顺便问下关于dynamic programming的。。

在一个graph里每个点代表一个地点，每两个点之间的开车所需时间都是已知的，出租车司机需要根据request到各个点接人送人，现在input是一个set X，每个elemet是一个（x,y,t）的组合，x是出发点，y是目的地，t是出发时间，司机一次只能招待一位乘客。现在要求这个出租车司机最多能接待的乘客量。。应该怎么思考这个问题。。。


[解决办法]
设修改的边为 e，则：
情况1：e 在 S 内，S不改变
情况2：e 不在 S 内。
1.将 e 添加至 S 中，此时会产生一个环。
2.取环中 cost 最大的边，与 e 修改后的 cost 比较。
3.若 e.cost 更小，则在 S 中删除此边，否则删除 e（即S保持不变）。
证明：
情况1：略
情况2：若 e 添加至 S 中，考虑再执行一次 kruskual 算法(与生成S时的kruskual比较)，在添加 e 至解之前情况相同，而对于环内的边，一定是删除后的那条边最后添加(它的cost最大），对于环外的边不影响添加情况。所以最后结果是到添加删除边的时候发现不可添加(已添加了e，将出现环），然后与原来添加情况一样，将剩下的边添加到解中，所以解即为上述算法的出的结果。
若 e 不添加到 S 中，则 S 仍为解。（证明方法与上相同）

注意,上述算法并未得到程序验证……只是鄙人脑想而已……
[解决办法]
若e在S内，且变得更大，则令G'=G-S
1.若G'为空，则MST为S;否则，在G'中寻找最小的边f.
2.若f>=e，则停止搜索，S为MST；若f<e,则判断f与e是否在同一个环路中，若在同一个环路中，则S-e+f为最小生成树。否则，执行3.
3.G'=G'-f,返回1循环。

ps:在寻找环路的时候可以使用剪枝法，即去掉图中只有一条边的点，重复这一去除过程即得到环路。