【問題描述】

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

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

??? 政府審批的規則如下：

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

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

?

?

?

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

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

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

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

【輸入】

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

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

【輸出】

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

【樣例】

?????? road.in?? ?????? ?????? ?????? road.out ?????? ?????? ?????? 修建的公路如圖所示：

?????? 4???? ?????? ?????? ?????? ?????? 6.47

?????? 0 0

?????? 1 2

?????? -1 2

?????? 0 4

【問題分析】

?????? 三條規則中的第二條是故弄玄虛。如果三個或三個以上的城市申請修建的公路成環，那么這些公路的長度必然都相同，否則不滿足“每個城市選擇一個與它最近的城市，申請修建通往該城市的公路”。所以，如果成環，其實是任意去掉一條路。

?

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #define M 5010 using namespace std; int fa[M],n,cnt; double x[M],y[M]; struct node {int x,y;double v; };node e[M*M]; double init(int i,int j) {cnt++;e[cnt].x=i;e[cnt].y=j;e[cnt].v=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } int cmp(const node&x,const node&y) {return x.v<y.v; } int found(int x) {if(fa[x]==x)return x;else return fa[x]=found(fa[x]); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]),fa[i]=i;for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)init(i,j);sort(e+1,e+cnt+1,cmp);double ans=0;for(int i=1;i<=cnt;i++){int a=found(e[i].x);int b=found(e[i].y);if(a!=b){ans+=e[i].v;fa[a]=b;}}printf("%.2lf",ans);return 0; } View Code

?

轉載于:https://www.cnblogs.com/harden/p/5596827.html

總結

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

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