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

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
最小生成樹(shù)
海之魂(cnitpm.com) 09:08:43
A
泉州-小盧(cnitpm.com) 09:09:41
可以說(shuō)下計(jì)算過(guò)程嗎
隨風(fēng)飄搖(cnitpm.com) 09:10:50
A
海之魂(cnitpm.com) 09:10:56
看看最小生成樹(shù)算法
2013下-林顯鐘(cnitpm.com) 09:10:59 

隨風(fēng)飄搖(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
都可以選，算的時(shí)候算一個(gè)6
隨風(fēng)飄搖(cnitpm.com) 09:13:51
和v1相連的距離都比較短
隨風(fēng)飄搖(cnitpm.com) 09:15:01
這題也可以逐漸去掉最遠(yuǎn)的線路
泉州-小盧(cnitpm.com) 09:15:42
那按找最短的話 先是v1v2
泉州-小盧(cnitpm.com) 09:15:49
那接下去呢
2013下-林顯鐘(cnitpm.com) 09:17:48
已經(jīng)抵達(dá)的點(diǎn)的其他線路，刪掉。繼續(xù)找到其他點(diǎn)的最短線路
風(fēng)中飄曳(cnitpm.com) 09:18:17
感覺(jué) 是50
2013下-林顯鐘(cnitpm.com) 09:18:22
看看最小生成樹(shù)原理吧，過(guò)一遍就了解了
泉州-小盧(cnitpm.com) 09:19:06 
理解不過(guò)來(lái)
泉州-小盧(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 

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

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

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

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

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