经纬度(cnitpm.com) 14:42:22
请教:最小生成树的问题
经纬度(cnitpm.com) 14:42:26
某地区的通信线路图如下图所示，假设其中标注的数字代表通信线路的长度（单位为千米），至少要假设（）长的线路，才能保持6个城市的通信连通。 

A、50
B、53
C、57
D、48

似衡(cnitpm.com) 14:45:22
51
经纬度(cnitpm.com) 14:45:58
答案:50
命中注定(cnitpm.com) 14:46:04
50？
nlist(cnitpm.com) 14:46:16
关键是怎么计算
经纬度(cnitpm.com) 14:46:23
怎么算的?
似衡(cnitpm.com) 14:46:25
对是50
命中注定(cnitpm.com) 14:46:26
10+11+6+5+18
似衡(cnitpm.com) 14:46:29
早最少
似衡(cnitpm.com) 14:46:32
找最少
arfeng(cnitpm.com) 14:46:47
54
似衡(cnitpm.com) 14:46:55
V0到V1你找最少的
似衡(cnitpm.com) 14:47:31
找最短路径
经纬度(cnitpm.com) 14:48:15
v0-v1是10
似衡(cnitpm.com) 14:48:27
V1-V2是5
似衡(cnitpm.com) 14:48:33
V2-V3是6
似衡(cnitpm.com) 14:48:47
也可以是V1-V3
似衡(cnitpm.com) 14:48:49
都是6
似衡(cnitpm.com) 14:49:14
到V4的最短距离是18
似衡(cnitpm.com) 14:49:30
到V5的最短距离是11
似衡(cnitpm.com) 14:49:35
加起来就是50
括弧(cnitpm.com)(cnitpm.com) 14:49:43
50
经纬度(cnitpm.com) 14:50:05
为什么不取v3-v5的路径呢? 14比18小啊
似衡(cnitpm.com) 14:50:34
V1到V5更小
似衡(cnitpm.com) 14:50:35
是11
似衡(cnitpm.com) 14:50:53
之前V0到V3都已经连接上了
似衡(cnitpm.com) 14:51:15
是已经连接的和未连接的点的距离
似衡(cnitpm.com) 14:52:14
明白了么？
似衡(cnitpm.com) 14:52:23
运筹学中有降到
似衡(cnitpm.com) 14:52:25
讲到
经纬度(cnitpm.com) 14:52:36
但这个路径并没有封闭啊
nlist(cnitpm.com) 14:52:45
不错
似衡(cnitpm.com) 14:52:54
封闭是什么意思？
命中注定(cnitpm.com) 14:53:03
没人要求要封闭呀
nlist(cnitpm.com) 14:53:08
题中又没有说一笔画
经纬度(cnitpm.com) 14:53:10
就是与v0连接
命中注定(cnitpm.com) 14:53:25
都能到达就可以了
似衡(cnitpm.com) 14:53:39
不用封闭啊，能连接所有的点即可
经纬度(cnitpm.com) 14:54:00
能到达是指通过邻近的点可以到达即可?
似衡(cnitpm.com) 14:54:14
题干说的是通讯联通