某省6个城市(A~F)之间的网络通信线路(每条通信线路旁标注了其长度公里数)如图2－13所示。如果要将

某省6个城市(A～F)之间的网络通信线路(每条通信线路旁标注了其长度公里数)如图2-13所示。如果要将部分千兆通信线路改造成万兆通信线路，以提升各个城市网络之间的通信容量，则至少要改造总计(66)公里的通信线路，这种总公里数最少的改造方案共有(67)个。

A．1000

B．1300

C．1600

D．2000

B解析：从图论上看，本题要求得到上图的最小支撑树(即选取部分边，使其保持连通，又使其总长度最小)。如下算法可以逐步实现这个要求。 任取一点，例如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、