大门|大门-CS-2015（第三组）|问题50

设G是100个顶点和300条边的连通无向图。G的最小生成树的权重为500。当G的每条边的权重增加5时，最小生成树的权重变为________。 （A） 1000 （B） 995 （C） 2000 （D） 1995 答复: （B） 说明： 因为有100个顶点，所以最小生成树（MST）中必须有99条边。

当每条边的重量增加5时，MST的重量增量为=99*5=495

所以MST的新重量是500+495，也就是995 这个问题的小测验