信管网综合知识

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

（1）A. 1000     
B. 1300     
C. 1600     
D. 2000 
（2）A. 1        
B. 2        
C. 3        
D. 4 
，第一题给的解析是算关键路径，不理解，求解释
11:25:35
小 2015-2-11 11:25:35

不是关键路径
小 2015-2-11 11:25:48

就是点到点间最短距离
DH 2015-2-11 11:26:31

嗯？那如何做
11:27:20
micke 2015-2-11 11:27:20

去边法
micke 2015-2-11 11:27:55

分两个集合处理
micke 2015-2-11 11:28:26

先确定a和非a两个集合
DH 2015-2-11 11:28:39

哦，不是很明白，谢谢哈，我先搜索下相关知识
micke 2015-2-11 11:29:02

然后取这两个集合最短关联路径
11:29:12
小 2015-2-11 11:29:12

方法我倒不确定，就是找两点间最短，然后所有点都连接上就ok了
micke 2015-2-11 11:29:26

把节点加入a集合
micke 2015-2-11 11:30:11

以此类推，直到全部节点都加入a集合
心 2015-2-11 11:31:10

从A开始，取最短权值 ，完后加入相应节点。以此类推 。包含所有节点，不形成回路就行了
11:33:04
2015上-苗 2015-2-11 11:33:04

@DHB 问一下那套题目答案是不是B,B？
DH 2015-2-11 11:33:29

答案给的是B、C
DH 2015-2-11 11:34:22

最短怎么是1300啊，哪个路径？
2015上-苗 2015-2-11 11:34:24

对的
2015上-苗 2015-2-11 11:34:28

是1300
11:35:26
2015上-苗 2015-2-11 11:35:26

ab,ae,fd,cd
2015上-苗 2015-2-11 11:35:29

是确定的
2015上-苗 2015-2-11 11:35:43

然后af一种
2015上-苗 2015-2-11 11:35:47

bf一种
DH 2015-2-11 11:36:37

嗯，谢谢
DH 2015-2-11 11:36:53

好难哈
11:39:27
micke 2015-2-11 11:39:27 


11:43:13
DH 2015-2-11 11:43:13

嗯，把最大边去掉，然后图中没有闭环？
11:57:17
micke 2015-2-11 11:57:17

不是去掉最大边
micke 2015-2-11 11:57:30

是取最小边
DH 2015-2-11 11:57:50

哦
2015上-苗 2015-2-11 11:58:10

我觉得第2问应该是b
2015上-苗 2015-2-11 11:58:17

ab是确定的
2015上-苗 2015-2-11 11:58:22

如果如上图所化
2015上-苗 2015-2-11 11:58:26

画
2015上-苗 2015-2-11 11:58:34

那么只有1000
2015上-苗 2015-2-11 11:58:38

哪来1300
2015上-苗 2015-2-11 11:58:50

只有af和bf可选
11:59:18
micke 2015-2-11 11:59:18

三个虚线
micke 2015-2-11 11:59:43

取两个
2015上-苗 2015-2-11 12:00:53

哦
2015上-苗 2015-2-11 12:00:55

对了对了
2015上-苗 2015-2-11 12:00:58

哎呀
2015上-苗 2015-2-11 12:01:01

谢谢
micke 2015-2-11 12:01:02

才能联通