下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。

admin2009-03-25  48

问题 下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。


选项 A、1
B、2
C、3
D、4

答案C

解析 从图论上看,本题要求得到上图的最小支撑树(即选取部分边,使其保持连通,又使其总长度最小)。
   如下算法可以逐步实现这个要求。
   任取一点,例如A,将其纳入已完成部分。点A与其他各点中的最小距离为AE=200,从而将边AE以及点E纳入已完成部分。
   点A、E与其他各点B、C、D、F这两个集合之间的最段距离为AB=AF=300,从而可以将边AB与点B(或边AF与点F)纳入已完成部分。
   点A、B、E与点C、D、F两个集合的最短距离为AF=BF=300,从而可以将边AF(或边BF)与点F纳入已完成部分。
   点A、B、E、F与点C、D两个集合之间的最段距离为FD=200,从而将边FD与点D纳入已完成部分。
   点A、B、E、F、D与点C两个集合之间的最短距离为CD=300,从而将边CD与点C纳入已完成部分。
   此时,所有6个点都已经接通,其边为AE、AB、AF、FD、CD,总长度为1300(如下图所示)。
   
   连通这6个点的边至少需要5条,最短总长等于2个200以及3个300。图中共有4条边长300,其中,CD边在最短总长度方案中不可缺少,而AB、BF、AF中可以任选2条。因此,共有3个最短总长度的方案。除了上面给出的外,还可以有两种(如下图所示):
   
转载请注明原文地址:https://jikaoti.com/ti/xHy7FFFM
0

随机试题
最新回复(0)