大门|大门-CS-2015（第1组）|问题53

下图显示了具有不同整数边权重的8条边。最小生成树（MST）的权重为36，包含以下边：{（A，C），（B，C），（B，E），（E，F），（D，F）}。下图中仅给出了MST中那些边的边权重。此图的所有8条边的最小可能权重之和为。

（A） 66 （B） 69 （C） 68 （D） 70 答复: （B） 说明： 在每个循环中，不属于MST的边的权重必须大于或等于属于MST的其他边的权重。

由于所有边权重都是不同的，因此权重必须更大。

所以ED的最小可能重量是7，CD的最小可能重量是16，AB的最小可能重量是10。

因此，最小可能的权重之和是69。 这个问题的小测验