P1265 公路修建 最小生成樹

2022-09-22 22:36:49 字數 979 閱讀 9938

(一句話題意的話,這題就不用做了)

某國有n個城市,它們互相之間沒有公路相通,因此交通十分不便。為解決這一“行路難”的問題,**決定修建公路。修建公路的任務由各城市共同完成。

修建工程分若干輪完成。在每一輪中,每個城市選擇一個與它最近的城市,申請修建通往該城市的公路。**負責審批這些申請以決定是否同意修建。

**審批的規則如下:

(1)如果兩個或以上城市申請修建同一條公路,則讓它們共同修建;

(2)如果三個或以上的城市申請修建的公路成環。如下圖,a申請修建公路ab,b申請修建公路bc,c申請修建公路ca。則**將否決其中最短的一條公路的修建申請;

(3)其他情況的申請一律同意。

當所有城市被組合成一個“城市聯盟”時,修建工程也就完成了。

你的任務是根據城市的分佈和前面講到的規則,計算出將要修建的公路總長度。

範圍&性質:\(1\le n\le 5000\)

除了第二種情況以外,別的顯然是最小生成樹的性質,那麼我們考慮第二種情況,由於每個城市都申請修建離自己最近的一條,所以成環的本質就是存在三個或以上的城市兩兩距離相等,此時每一條都可以看成最短的,也不影響最小生成樹

tips:由於兩兩城市之間都有一條邊,形成了一個完全圖,所以採用prim演算法,但是又因為n過大,鄰接矩陣存不下,所以在prim更新的時候再算一下距離(我就這樣mle了幾次)

#includeusing namespace std;

namespace zzc

a[maxn];

double calc(int s,int t)

void prim()

dis[1]=0;

for(int k=1;k<=n;k++)

}} }

void work()

prim();

printf("%.2lf",ans); }

} int main()

P1265 公路修建 最小生成樹

某國有n個城市,它們互相之間沒有公路相通,因此交通十分不便。為解決這一 行路難 的問題, 決定修建公路。修建公路的任務由各城市共同完成。 修建工程分若干輪完成。在每一輪中,每個城市選擇一個與它最近的城市,申請修建通往該城市的公路。 負責審批這些申請以決定是否同意修建。 審批的規則如下 1 如果兩個或...

P1265 公路修建 prim

題目描述 某國有n個城市,它們互相之間沒有公路相通,因此交通十分不便。為解決這一 行路難 的問題, 決定修建公路。修建公路的任務由各城市共同...

Luogu P1265 公路修建

luogu p1265 本來一開始我用的kruskal 但是由於double型別8位元組,所以mle了。 很容易發現這是一道最小生成樹的題目。 值得注意的是題目中給的第二個限制,只存在唯一情況即這個環為等邊多邊形。 但是如果是等邊多邊形那麼這個限制給了和沒給完全沒區別 所以這就是一道最小生成樹裸題。 ...