C++算法題,圖論問題,給定N個頂點及M條邊,求能使所有頂點連通,且最大邊與最小邊之差最小
也就是這個
xxx國“山頭鄉(xiāng)”有n個村子,政府準備修建鄉(xiāng)村公路,由于地形復雜,有些鄉(xiāng)村之間可能無法修筑公路,因此政府經(jīng)過仔細的考察,終于得到了所有可能的修路費用數(shù)據(jù).并將其公布于眾,廣泛征求村民的修路意見.嗯,xxx國真是一個平等的國度.
政府考慮到費用問題,因此要求只能建n-1條公路,而且這n-1條公路還能連通n個村子,而且調查數(shù)據(jù)表明,這完全是可行的.
村民們展開了激烈的討論,最后大家達成一致,要求每條路的費用要盡可能一樣,這是基于“平等”的考慮,汗~
xxx國政府頭腦簡單,這這,太難了,最后雙方又達成一致,那就保證費用最大的那條與費用最小的那條之間的費用之差盡可能最小吧.
現(xiàn)在的問題就交給你了,要你找出滿足以上條件的一種方案,你只要輸出費用最大的那條公路與費用最小的那條公路之間費用的差值w即可.嗯,因為這個數(shù)據(jù)還得告知村民,還是要“平等”.