相信大家都聽說一個“百島湖”的地方吧，百島湖的居民生活在不同的小島中，當他們想去其他的小島時都要通過劃小船來實現。現在政府決定大力發展百島湖，發展首先要解決的問題當然是交通問題，政府決定實現百島湖的全暢通！經過考察小組RPRush對百島湖的情況充分了解后，決定在符合條件的小島間建上橋，所謂符合條件，就是2個小島之間的距離不能小于10米，也不能大于1000米。當然，為了節省資金，只要求實現任意2個小島之間有路通即可。其中橋的價格為 100元/米。

Input

輸入包括多組數據。輸入首先包括一個整數T(T <= 200)，代表有T組數據。?
每組數據首先是一個整數C(C <= 100),代表小島的個數，接下來是C組坐標，代表每個小島的坐標，這些坐標都是 0 <= x, y <= 1000的整數。?

Output

每組輸入數據輸出一行，代表建橋的最小花費，結果保留一位小數。如果無法實現工程以達到全部暢通，輸出”oh!”.

Sample Input

2 2 10 10 20 20 3 1 1 2 2 1000 1000

Sample Output

1414.2 oh!

C++版本一

參考https://blog.csdn.net/weixin_43272781/article/details/83588706

最小生成樹，用kruskal求解,此題特別之處，給出的位置是坐標的形式，需把它轉化為求最小生成樹的一般位置形式。?

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h>using namespace std; const int N=10000+10; int t,n,m,pre[N]; struct node{int x,y;node(){};node(int a, int b){x=a;y=b;} }point[N]; double L(int x,int y,int x2,int y2){return sqrt(abs((x-x2)*(x-x2)+(y-y2)*(y-y2)));} struct Edge{int f,t;double l;Edge(){};Edge(int a, int b,double c){f=a;t=b;l=c;}bool operator <(const Edge &S)const{return l<S.l;} }e[N]; int find(int x){int r=x;while(pre[r]!=r)r=pre[r];return r;} void join(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy)pre[fx]=fy;} int main() {scanf("%d",&t);while(t--){scanf("%d",&n);int a,b;for(int i=1;i<=n;i++){scanf("%d%d",&a,&b);point[i]=node(a,b);}int cnt=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){e[++cnt]=Edge(i,j,L(point[i].x,point[i].y,point[j].x,point[j].y));}}sort(e+1,e+cnt+1);for(int i=1;i<=n;i++){pre[i]=i;}double ans=0;for(int i=1;i<=cnt;i++)if(find(e[i].f)!=find(e[i].t)&&e[i].l>=10.0&&e[i].l<=1000.0){join(e[i].f,e[i].t);ans+=e[i].l;}int cn=0;for(int i=1;i<=n;i++)if(pre[i]==i)cn++;if(cn-1==0)printf("%.1lf\n",ans*100);elsecout << "oh!" << endl;}//cout << "Hello world!" << endl;return 0; }

C++版本二

//HDU 1875 AC #include <iostream> #include <cmath>using namespace std; #define MAX 100010 #define LEN 105 double dist[LEN]; double map[LEN][LEN]; bool isvisited[LEN];//點的結構體 typedef struct Point{double x;double y; }Point;//初始化 void init(){int i,j;for(i=0;i<LEN;i++){for(j=0;j<LEN;j++){if(i==j) map[i][j]=0; //對a[][]進行初始化，一般都要；map[i][j]=MAX;}} }//計算兩點距離 double caculteD(Point a,Point b){double len;len=sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));return len;}//prim算法 double prim(int n){int i,j,min,pos;double sum=0;memset(isvisited,false,sizeof(isvisited));//初始化for(i=1;i<=n;i++){dist[i]=map[1][i];}//從1開始isvisited[1]=true;dist[1]=MAX;//找到權值最小點并記錄下位置for(i=1;i<n;i++){min=MAX;//pos=-1;for(j=1;j<=n;j++){if(!isvisited[j] && dist[j]<min){min=dist[j];pos=j;}} if(min==MAX){return -1;}sum+=dist[pos];//加上權值isvisited[pos]=true;//更新權值for(j=1;j<=n;j++){if(!isvisited[j] && dist[j]>map[pos][j]){dist[j]=map[pos][j];}}} return sum; }int main(){Point p[105];int i,j,n,nCase;cin>>nCase;double result;//總價while(nCase--){cin>>n;init(); //初始化for(i=1;i<=n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}for(i=1;i<n;i++){for(j=i+1;j<=n;j++){ double len;len=caculteD(p[i],p[j]);if(len>=10 && len<=1000){//長度有限制map[i][j]=map[j][i]=100*len;//要*100 } }}result=prim(n);if(result==-1){cout<<"oh!"<<endl;}else{printf("%.1lf\n",result);}}return 0; }

C++版本三

這道題做了好久 主要是問題在于 浮點數的處理。?
剛開始做意識到 肯定用浮點數來存值 ，但將所有變量都用 浮點數定義時?
使用memset 函數對Map 數組初始化為最大時 結果發生了變化

總之 只要處理好 浮點數的關系 其實這道題還是挺容易的

#include <iostream> #include <cstring> #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std;double Map[1005][1005],dis[1005]; int M,visit[1005],flag;struct node {double x, y; }st[1005]; void prim() {flag=0;for(int i = 1;i <= M; i++){dis[i] = Map[i][1];}dis[1] = 0;visit[1] = 1;double sum = 0.0;for(int i = 1; i <= M-1; i++){double temp = INF;int pos;for(int j= 1; j <= M; j++){if(!visit[j] && temp > dis[j]){temp = dis[j];pos = j;}}if(temp == INF){flag = 1;break;}sum += dis[pos];visit[pos] = 1;for(int j = 1; j <= M; j++){if(!visit[j] && Map[pos][j] < dis[j] && Map[pos][j]!=INF){dis[j] = Map[pos][j];}}}if (!flag)printf("%.1lf\n",sum*100.0);elseprintf ("oh!\n"); } int main() {int N;scanf("%d",&N);while (N--){memset(visit,0,sizeof(visit));scanf("%d",&M);for(int i=1;i<=M;i++){for(int j=1;j<=M;j++){if(i==j)Map[i][j]=0;elseMap[i][j]=INF;}}for (int i=1; i<=M; i++){scanf("%lf %lf",&st[i].x,&st[i].y);for (int j=1; j<i; j++){double dis = sqrt((st[i].x-st[j].x)*(st[i].x-st[j].x)+(st[i].y-st[j].y)*(st[i].y-st[j].y));if (dis<Map[i][j]&&dis>=10&&dis<=1000){Map[i][j] = Map[j][i] = dis;}}}prim();} }

?

總結

以上是生活随笔為你收集整理的畅通工程再续的全部內容，希望文章能夠幫你解決所遇到的問題。

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