Problem Description 相信大家都聽說一個“百島湖”的地方吧，百島湖的居民生活在不同的小島中，當他們想去其他的小島時都要通過劃小船來實現。現在政府決定大力發展百島湖，發展首先要解決的問題當然是交通問題，政府決定實現百島湖的全暢通！經過考察小組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!

?

?

一代模板如下

AC代碼：（僅供參考）

?

1 #include<cstdio>2 #include<cmath>3 #include<cstring>4 #include<algorithm>5 6 using namespace std;7 8 #define N 1100009 10 int father[N];11 12 int sum;13 14 struct no15 {16 int x,y;17 }di[N];18 19 struct node20 {21 int s,e;22 double l;23 }dd[N];24 25 int Find(int n)26 {27 while(n!=father[n])28 n=father[n];29 30 return n;31 }32 33 void Fin(int x,int y)34 {35 int a,b;36 37 a=Find(x);38 b=Find(y);39 40 if(a!=b)41 {42 father[b]=a;43 sum++;44 }45 }46 47 bool cmp(node a, node b)48 {49 return a.l < b.l;50 }51 52 int main()53 {54 int t;55 56 scanf("%d",&t);57 58 while(t--)59 {60 int c;61 62 scanf("%d",&c);63 64 for(int i=0; i<=c; i++)65 father[i]=i;66 67 for(int i=0; i<c; i++)68 scanf("%d%d",&di[i].x, &di[i].y);69 70 if(c==1)71 {72 printf("0.0\n");73 continue;74 }75 76 int k=0;77 78 for(int i=0; i<c; i++)79 for(int j=i+1; j<c; j++)80 {81 double mi=sqrt((double)(di[i].x-di[j].x)*(di[i].x-di[j].x)+(double)(di[i].y-di[j].y)*(di[i].y-di[j].y));82 83 if(mi >= 10 && mi <= 1000)84 {85 dd[k].s=i;86 dd[k].e=j;87 dd[k].l=mi;88 k++;89 }90 }91 92 sort(dd,dd+k,cmp);93 94 sum=1;95 double sun=0;96 97 for(int i=0; i<k; i++)98 if(Find(dd[i].s) != Find(dd[i].e))99 { 100 Fin(dd[i].s,dd[i].e); 101 sun+=dd[i].l; 102 } 103 104 if(sum < c) 105 printf("oh!\n"); 106 else 107 printf("%.1lf\n",sun*100); 108 109 } 110 return 0; 111 } View Code

?

?

不甘心，自己再來一

?

1 #include<cstdio>2 #include<cmath>3 #include<cstring>4 #include<algorithm>5 6 using namespace std;7 8 #define N 1100009 10 int p[N], s; 11 12 struct data 13 { 14 int x, y; 15 }v[N]; 16 17 struct node 18 { 19 int a, b; 20 double l; 21 }d[N]; 22 23 bool cmp(node a, node b) 24 { 25 return a.l < b.l; 26 } 27 28 int Find(int x) 29 { 30 while(p[x] != x) 31 x = p[x]; 32 33 return x; 34 } 35 36 void Fin(int x, int y) 37 { 38 int a = Find(x); 39 int b = Find(y); 40 41 if (a != b) 42 { 43 s++; 44 p[b] = a; 45 } 46 } 47 48 int main() 49 { 50 int T; 51 scanf ("%d", &T); 52 53 while (T--) 54 { 55 int n; 56 57 scanf ("%d", &n); 58 59 for (int i = 0; i <= n; i++) 60 p[i] = i; 61 62 for (int i = 0; i < n; i++) 63 scanf ("%d %d", &v[i].x, &v[i].y); 64 65 int k = 0; 66 67 for (int i = 0; i < n; i++) 68 for (int j = i+1; j < n; j++) 69 { 70 double mi =sqrt((double)(v[i].x - v[j].x)*(v[i].x - v[j].x) + (double)(v[i].y - v[j].y)*(v[i].y - v[j].y)); 71 72 if (mi >= 10 && mi <= 1000) 73 { 74 d[k].a = i; 75 d[k].b = j; 76 d[k].l = mi; 77 k++; 78 } 79 } 80 81 double num = 0; 82 s = 0; 83 sort(d, d+k, cmp); 84 85 for (int i = 0; i < k; i++) 86 if (Find(d[i].a) != Find(d[i].b)) 87 { 88 num += d[i].l; 89 Fin(d[i].a, d[i].b); 90 } 91 92 if (s < n-1) 93 printf ("oh!\n"); 94 else 95 printf ("%.1f\n", 100*num); 96 } 97 return 0; 98 } View Code

?

?

轉載于:https://www.cnblogs.com/Aa948766160/p/5749952.html

總結

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

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