某地区的通信线路图如下,假设其中标注的数字代表通信线路的长度(单位:千米),现在要求至少要架设()的线路,才能保持6个城市的通信连通。
参考答案
C
答案解析
此类题型解题的算法:在保证无回路的前提下选择(n-1)条最小权边。分析题目,要求至少假设多长的线路才能保持通信连通,也就意味着途中ABCDEF六个点之间能够全部连接起来,且连接长度最短即可。因此,在铺设线路过程中,首先要考虑先连通两点之间最短的,然后考虑次之,直到刚好连通为止。
第一步:选择最小权边200,AE、DF连通。
第二部:选择最小权边300(200选完之后,最小的权边是300),有AB、BF、AF、CD。
第三步:由于AB、AF、BF之间构成了回路,所以,这三条线路至少剔除一条。
这样,在图中就有两个200的线路和三个300的线路。
因此,至少铺设1300公里的线路。
本题关键在于确定解题的算法和画图分析。
第一步:选择最小权边200,AE、DF连通。
第二部:选择最小权边300(200选完之后,最小的权边是300),有AB、BF、AF、CD。
第三步:由于AB、AF、BF之间构成了回路,所以,这三条线路至少剔除一条。
这样,在图中就有两个200的线路和三个300的线路。
因此,至少铺设1300公里的线路。
本题关键在于确定解题的算法和画图分析。
你可能感兴趣的试题
A.64
B.74
C.76
D.68
A.21
B.34
C.39
D.48