单选题
下图标明了六个城市(A～F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路，使各个城市之间均可通过高速公路通达，至少要改造总计 (9) 公里的公路，这种总公里数最少的改造方案共有 (10) 个。
单选题
A．1000 B．1300 C．1600 D．2000
【正确答案】
B
【答案解析】
单选题
A．1 B．2 C．3 D．4
【正确答案】
C
【答案解析】[解析] 这是一道求图的最小生成树问题，我们使用克鲁斯卡尔算法来解答，如下图所示。
到了第5步，就有了多种选择，既可以选择AF，也可以选择BF，因为其路程都是300公里。我们给出的第6步是选择AF的结果。还有一种结果，就是在第4步时，不是选择AB，而是选择AF或BF，则结果如图14-27所示。
从第6步的结果可以计算出，至少要改造的公路长度为200×2+300×3=1300(公里)。
到了第5步，就有了多种选择，既可以选择AF，也可以选择BF，因为其路程都是300公里。我们给出的第6步是选择AF的结果。还有一种结果，就是在第4步时，不是选择AB，而是选择AF或BF，则结果如图14-27所示。
从第6步的结果可以计算出，至少要改造的公路长度为200×2+300×3=1300(公里)。