題目描述

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

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

政府審批的規則如下：

（1）如果兩個或以上城市申請修建同一條公路，則讓它們共同修建；

（2）如果三個或以上的城市申請修建的公路成環。如下圖，A申請修建公路AB，B申請修建公路BC，C申請修建公路CA。則政府將否決其中最短的一條公路的修建申請；

（3）其他情況的申請一律同意。

一輪修建結束后，可能會有若干城市可以通過公路直接或間接相連。這些可以互相：連通的城市即組成“城市聯盟”。在下一輪修建中，每個“城市聯盟”將被看作一個城市，發揮一個城市的作用。

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

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

輸入格式

第一行一個整數n，表示城市的數量。(n≤5000)

以下n行，每行兩個整數x和y，表示一個城市的坐標。(-1000000≤x，y≤1000000)

輸出格式

一個實數，四舍五入保留兩位小數，表示公路總長。（保證有惟一解）

輸入輸出樣例

輸入 #1復制 4 0 0 1 2 -1 2 0 4 輸出 #1復制 6.47

說明/提示

修建的公路如圖所示：

?

解析：

MST裸題(不接受挨打)

由于是稠密圖，所以采用了Prim算法
(稀疏圖最好用克魯斯卡爾)
對任意兩個點都求出距離
然后對其跑一遍最小生成樹
但是注意n的范圍是5000，而大小限制為125MB

題目本身不難，但是會一直MLE，所以需要優化

我這里有三個代碼，不同的分數

第一個是裸的開 5000*5000 double數組的Prim算法可以跑出80分的好成績(不開O2)。、

第二個是裸的克魯斯卡爾算法，不開O2估計70分，開了O2穩定80分，運氣好的話就是90分

第三個就是Prim，與第一個Prim不同的是會減少大量的冗余運算，具體體現就是把 5000 * 5000 的數組取消掉

只會在需要計算的時候才會計算，將大大減少時間和內存，，，所以就AC了。

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 #include<iomanip> 8 #include<cstdlib> 9 #include<queue> 10 #include<set> 11 #include<map> 12 #include<stack> 13 #include<vector> 14 #define LL long long 15 #define re register 16 #define INF 0x7fffffff 17 #define Max 5002 18 #define D double 19 inline int read() 20 { 21 int s=0,f=-1;char ch=getchar(); 22 while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} 23 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); 24 return s*f; 25 } 26 int n;D ans=0.0,g[Max][Max],dis[Max]; 27 bool vis[Max]={0}; 28 struct edge { 29 D x,y; 30 }t[Max]; 31 D Dis(D x1,D y1,D x2,D y2) 32 { 33 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 34 } 35 int main() 36 { 37 scanf("%d",&n); 38 for(re int i = 1 ; i <= n ; ++ i) g[i][i]=0,scanf("%lf%lf",&t[i].x,&t[i].y); 39 for(re int i = 1 ; i <= n ; ++ i) 40 for(re int j = i+1 ; j <= n ; ++ j) 41 g[i][j]=g[j][i]=Dis(t[i].x,t[i].y,t[j].x,t[j].y); 42 int pos;vis[1]=1; 43 for(re int i = 1 ; i <= n ; ++ i) dis[i]=g[1][i]; 44 for(re int i = 1 ; i < n ; ++ i) { 45 pos=0; 46 for(re int j = 1 ; j <= n ; ++ j) { 47 if(vis[j]==1) continue; 48 if(!pos || dis[j] < dis[pos]) pos=j; 49 } 50 vis[pos]=1; 51 ans+=dis[pos]; 52 for(re int j = 1 ; j <= n ; ++ j) { 53 if(vis[j]==1) continue; 54 dis[j]=std::min(dis[j],g[pos][j]); 55 } 56 } 57 printf("%.2lf",ans); 58 return 0; 59 } 80分裸的Prim 1 // luogu-judger-enable-o2 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<string> 7 #include<algorithm> 8 #include<iomanip> 9 #include<cstdlib> 10 #include<queue> 11 #include<set> 12 #include<map> 13 #include<stack> 14 #include<vector> 15 #define LL long long 16 #define re register 17 #define Max 5000*5000/2 18 #define D double 19 inline int read() 20 { 21 int s=0,f=-1;char ch=getchar(); 22 while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} 23 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); 24 return s*f; 25 } 26 int n,pa[Max];D ans=0; 27 struct edge { 28 D x,y; 29 }t[Max]; 30 struct DIS { 31 D dis; 32 int from,to; 33 friend bool operator<(DIS a,DIS b) { 34 return a.dis<b.dis; 35 } 36 }e[Max]; 37 int find(int x) 38 { 39 if(x!=pa[x]) pa[x]=find(pa[x]); 40 return pa[x]; 41 } 42 void join(int x,int y) 43 { 44 x=find(x);y=find(y); 45 pa[y]=x; 46 } 47 D Dis(D x1,D y1,D x2,D y2) 48 { 49 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 50 } 51 int main() 52 { 53 scanf("%d",&n);int cnt=0; 54 for(re int i = 1 ; i <= n ; ++ i) pa[i]=i,scanf("%lf%lf",&t[i].x,&t[i].y); 55 for(re int i = 1 ; i <= n ; ++ i) 56 for(re int j = i+1 ; j <= n ; ++ j) 57 e[++cnt].dis=Dis(t[i].x,t[i].y,t[j].x,t[j].y),e[cnt].from=i,e[cnt].to=j; 58 int k=0; 59 std::sort(e+1,e+1+cnt); 60 for(re int i = 1 ; i <= cnt ; ++ i) { 61 int x=e[i].from,y=e[i].to;D t=e[i].dis; 62 if(find(x)!=find(y)) join(x,y),ans+=t; 63 if(k==n-1) break; 64 } 65 printf("%.2lf",ans); 66 return 0; 67 } 開O2或許是90分或許是80分，看你是否臉黑 1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 #include<iomanip> 8 #include<cstdlib> 9 #include<queue> 10 #include<set> 11 #include<map> 12 #include<stack> 13 #include<vector> 14 #define LL long long 15 #define re register 16 #define INF 0x7fffffff 17 #define Max 5002 18 #define D double 19 inline int read() 20 { 21 int s=0,f=-1;char ch=getchar(); 22 while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} 23 while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); 24 return s*f; 25 } 26 int n;D ans=0.0,dis[Max]; 27 bool vis[Max]={0}; 28 struct edge {D x,y;}t[Max]; 29 D Dis(D x1,D y1,D x2,D y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} 30 int main() 31 { 32 scanf("%d",&n); 33 for(re int i = 1 ; i <= n ; ++ i) dis[i]=INF,scanf("%lf%lf",&t[i].x,&t[i].y); 34 int pos;dis[1]=0; 35 for(re int i = 1 ; i <= n ; ++ i) { 36 D m=INF*1.0; 37 for(re int j = 1 ; j <= n ; ++ j) 38 if(dis[j] < m && !vis[j]) m=dis[j],pos=j; 39 vis[pos]=1; 40 ans+=m; 41 for(re int j = 1 ; j <= n ; ++ j) { 42 if(vis[j]==1) continue; 43 D d=Dis(t[pos].x,t[pos].y,t[j].x,t[j].y); 44 dis[j]=std::min(dis[j],d); 45 } 46 } 47 printf("%.2lf",ans); 48 return 0; 49 } AC 代碼

轉載于:https://www.cnblogs.com/handsomegodzilla/p/11291039.html

總結

以上是生活随笔為你收集整理的洛谷P1265 公路修建题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。