泉州-小盧(cnitpm.com) 09:06:16
某地區(qū)的通信線路圖如下圖所示，假設(shè)其中標注的數(shù)字代表通信線路的長度（單位為千米），至少要假設(shè)（）長的線路，才能保持6個城市的通信連通。 

A、50
B、53
C、57
D、48
這題如何做 啊
泉州-小盧(cnitpm.com) 09:06:21
求指導(dǎo)
Mars&Vs(cnitpm.com) 09:08:08
A
2013下-林顯鐘(cnitpm.com) 09:08:14
最小生成樹
海之魂(cnitpm.com) 09:08:43
A
泉州-小盧(cnitpm.com) 09:09:41
可以說下計算過程嗎
隨風飄搖(cnitpm.com) 09:10:50
A
海之魂(cnitpm.com) 09:10:56
看看最小生成樹算法
2013下-林顯鐘(cnitpm.com) 09:10:59 

隨風飄搖(cnitpm.com) 09:11:11
先架最短的
泉州-小盧(cnitpm.com) 09:12:06
最短是 v1 v2
泉州-小盧(cnitpm.com) 09:12:18
那接下去 有2條是6的啥辦、
泉州-小盧(cnitpm.com) 09:12:28
v1v3 v2v3
海之魂(cnitpm.com) 09:12:40
都可以選，算的時候算一個6
隨風飄搖(cnitpm.com) 09:13:51
和v1相連的距離都比較短
隨風飄搖(cnitpm.com) 09:15:01
這題也可以逐漸去掉最遠的線路
泉州-小盧(cnitpm.com) 09:15:42
那按找最短的話 先是v1v2
泉州-小盧(cnitpm.com) 09:15:49
那接下去呢
2013下-林顯鐘(cnitpm.com) 09:17:48
已經(jīng)抵達的點的其他線路，刪掉。繼續(xù)找到其他點的最短線路
風中飄曳(cnitpm.com) 09:18:17
感覺 是50
2013下-林顯鐘(cnitpm.com) 09:18:22
看看最小生成樹原理吧，過一遍就了解了
泉州-小盧(cnitpm.com) 09:19:06 
理解不過來
泉州-小盧(cnitpm.com) 09:21:48
那按找最短的話 先是v1v2
那接下去呢 是v1v3 還是v2
泉州-小盧(cnitpm.com) 09:21:50
v3
包大亭(cnitpm.com) 09:25:28

2013下-林顯鐘(cnitpm.com) 09:26:06 
v0
泉州-小盧(cnitpm.com) 09:33:37 

風中飄曳(cnitpm.com) 09:34:46 

包大亭(cnitpm.com) 09:35:21
選誰都行的@泉州-小盧
泉州-小盧(cnitpm.com) 09:35:55
那你選v2v3 整個畫線不是都變了
包大亭(cnitpm.com) 09:36:24
最后加起來還是一樣的
泉州-小盧(cnitpm.com) 09:38:23 

包大亭(cnitpm.com) 09:39:36 

泉州-小盧(cnitpm.com) 09:41:23 

餓狼傳說(cnitpm.com) 09:43:11
這個選V2V3也是可以的，那下次還是要從V0V1上面取，因為此時V1V3已經(jīng)通了
tan@(cnitpm.com) 09:43:59
你要是選V5 V4就不通了
餓狼傳說(cnitpm.com) 09:44:54
根據(jù)算法選不到V4V5的
餓狼傳說(cnitpm.com) 09:46:11
根據(jù)算法要選擇不在一個樹上的兩個結(jié)點
泉州-小盧(cnitpm.com) 09:46:25
這個不是通了嗎
貼地飛行(cnitpm.com) 09:47:17
19可以去掉了
鋼鐵怪show(cnitpm.com) 09:47:19
但是不是最優(yōu)的選擇吧？
→飄雪(cnitpm.com) 09:47:48
V2~V3和V1~V3是兩個選一個都可以啊，最短原理，所有的能連接一遍就可以了。問題是這個 很明顯存在問題，v0~v4這條線是多余的，還有是V1~V5比V3~V5短，為什么不取短的要取長的？
餓狼傳說(cnitpm.com) 09:48:00
最小路徑還是根據(jù)算法吧，算法是最合理的選擇
泉州-小盧(cnitpm.com) 09:49:30
說的我更亂了，我再想想 謝謝你們了