題意范例

1、1,10147: Highways,★★★☆☆題組：Problem Set Archive with Online Judge題號(hào)：10147: Highways解題者：李泳翰解題日期：2011年3月21日題意：政府想要新建一些高速公路連接各城鎮(zhèn)，使得任2個(gè)城鎮(zhèn)之間的來(lái)往都可以透過(guò)高速公路系統(tǒng)。 城鎮(zhèn)按照1到N來(lái)編號(hào)，並且給你每個(gè)城鎮(zhèn)的座標(biāo)。每條高速公路僅連接2個(gè)城鎮(zhèn)。所有的高速公路都是雙向且是直線的，其長(zhǎng)度為2城鎮(zhèn)座

2、標(biāo)的距離。 花費(fèi)的金錢(qián)與新建高速公路的長(zhǎng)度成正比。你的任務(wù)就是幫助他們找出該在哪些城鎮(zhèn)之間新建高速公路，並且使得花費(fèi)最低。,2,題意範(fàn)例：九個(gè)城鎮(zhèn)與先蓋好的三個(gè)高速公路。解法：Kruskal’s algorithm解法範(fàn)例：,3,,4,,5,完成圖像這樣,6,討論： (1)題目也沒(méi)要求印出最小距離，也就不用開(kāi)根號(hào)，還得宣告成double了。 (2)雖然用有向樹(shù)的資料結(jié)構(gòu)，不過(guò) 為了求出點(diǎn)與點(diǎn)之間的距離還是需要O(n