網頁

2014年3月16日 星期日

UVa 10369 Arctic Network

題意:
    有S個衛星,以及P個城市,如果兩個城市都有衛星的話,那麼不管距離多遠都能通訊,否則就只能靠radio通訊,而靠radio通訊的最遠的兩個城市距離為D,現在求如果每個城市都要通訊的話,那麼D最小為多少?
以Sample Input舉例:
(0,300)~(0,600)=300之間,各使用一個satellite,透過satellite來溝通,(0,100)~(0,300)=200和(0,600)~(150,750)=212.13則使用radio,因此D至少要212.13

想法:
    P個城市代表有(P-1)條邊,而用Kruskal演算法做出最小生成樹,做Kruskal的過程中將邊長記錄下來,共有(P-1)條,然後把其中最長的(S-1)條邊分配給衛星,剩下的邊的最大値就是D。