Total Submission(s): 31196 Accepted Submission(s): 10205
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!
Source
2008浙大研究生复试热身赛（2）——全真模拟
解题分析：
最小生成树模板题。
AC代码：
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<algorithm> 5 6 using namespace std; 7 8 #define N 105 9 #define inf 99999999 10 11 struct node{ 12 double x, y; 13 }s[N]; 14 struct edge{ 15 int u, v; 16 double w; 17 }t[10010]; 18 19 double f[N]; 20 21 int cmp(edge a, edge b) 22 { 23 return a.w < b.w; 24 } 25 26 int Find(int v) 27 { 28 if(f[v] == v) 29 return v; 30 f[v] = Find(f[v]); 31 return f[v]; 32 } 33 34 int Union(int u, int v) 35 { 36 int t1 = Find(u), t2 = Find(v); 37 if(t1 != t2) 38 { 39 f[t2] = t1; 40 return 1; 41 } 42 return 0; 43 } 44 45 int main() 46 { 47 int T, i, j, n, k, h, len; 48 double a, b, sum, Min, l; 49 scanf("%d", &T); 50 while(T--) 51 { 52 scanf("%d", &n); 53 len = h = 0; 54 for(i = 0; i <= n; i++) 55 f[i] = i; 56 for( i = 1; i <= n; i++) 57 scanf("%lf%lf", &s[i].x, &s[i].y); 58 for(i = 1; i <= n; i++) 59 { 60 for(j = 1; j < i; j++) 61 { 62 l = sqrt((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)); 63 t[len].u = i; 64 t[len].v = j; 65 t[len++].w = l; 66 } 67 } 68 sort(t, t+len, cmp); 69 for(i = 0, sum = 0; i < len && h < n-1; i++) 70 { 71 if(t[i].w >= 10 && t[i].w <= 1000 && Union(t[i].u, t[i].v)) 72 h++, sum += t[i].w; 73 } 74 if(h == n-1) 75 printf("%.1lf ", sum*100); 76 else 77 printf("oh! "); 78 } 79 return 0; 80 }