DHB
下圖標(biāo)明了六個(gè)城市（A～F ）之間的公路（每條公路旁標(biāo)注了其長度公里數(shù)）。為將部分公路改造成高速公路，使各個(gè)城市之間均可通過高速公路通達(dá)，至少要改造總計(jì)（1 ）公里的公路，這種總公里數(shù)最少的改造方案共有（2 ）個(gè)。

（1）A. 1000     
B. 1300     
C. 1600     
D. 2000 
（2）A. 1        
B. 2        
C. 3        
D. 4 
，第一題給的解析是算關(guān)鍵路徑，不理解，求解釋
11:25:35
小 2015-2-11 11:25:35

不是關(guān)鍵路徑
小 2015-2-11 11:25:48

就是點(diǎn)到點(diǎn)間最短距離
DH 2015-2-11 11:26:31

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

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

分兩個(gè)集合處理
micke 2015-2-11 11:28:26

先確定a和非a兩個(gè)集合
DH 2015-2-11 11:28:39

哦，不是很明白，謝謝哈，我先搜索下相關(guān)知識(shí)
micke 2015-2-11 11:29:02

然后取這兩個(gè)集合最短關(guān)聯(lián)路徑
11:29:12
小 2015-2-11 11:29:12

方法我倒不確定，就是找兩點(diǎn)間最短，然后所有點(diǎn)都連接上就ok了
micke 2015-2-11 11:29:26

把節(jié)點(diǎn)加入a集合
micke 2015-2-11 11:30:11

以此類推，直到全部節(jié)點(diǎn)都加入a集合
心 2015-2-11 11:31:10

從A開始，取最短權(quán)值 ，完后加入相應(yīng)節(jié)點(diǎn)。以此類推 。包含所有節(jié)點(diǎn)，不形成回路就行了
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啊，哪個(gè)路徑？
2015上-苗 2015-2-11 11:34:24

對(duì)的
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

嗯，把最大邊去掉，然后圖中沒有閉環(huán)？
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問應(yīng)該是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

三個(gè)虛線
micke 2015-2-11 11:59:43

取兩個(gè)
2015上-苗 2015-2-11 12:00:53

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

對(duì)了對(duì)了
2015上-苗 2015-2-11 12:00:58

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

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

才能聯(lián)通