http://acm.hdu.edu.cn/showproblem.php?pid=1875
题意：
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
思路：
又是畅通工程的题目，用来熟悉最小生成树的不错题目。
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<algorithm> 5 #include<vector> 6 #include<cmath> 7 using namespace std; 8 9 int n, cnt; 10 double ans; 11 int x[105], y[105]; 12 int num; 13 14 struct node 15 { 16 int u; 17 int v; 18 double dist; 19 }edge[105*105]; 20 21 int p[105]; 22 23 double cacl(int x1, int y1, int x2, int y2) 24 { 25 return sqrt((y2 - y1)*(y2 - y1) + (x2 - x1)*(x2 - x1)); 26 } 27 28 int find(int x) 29 { 30 return p[x] == x ? x : find(p[x]); 31 } 32 33 bool cmp(node a, node b) 34 { 35 return a.dist < b.dist; 36 } 37 38 void Kruskal() 39 { 40 num = 0; 41 for (int i = 0; i < cnt; i++) 42 { 43 int x = find(edge[i].u); 44 int y = find(edge[i].v); 45 if (x != y) 46 { 47 p[x] = y; 48 ans += edge[i].dist * 100; 49 num++; 50 if (num == n - 1) return; 51 } 52 } 53 } 54 55 int main() 56 { 57 //freopen("D:\\txt.txt", "r", stdin); 58 int T; 59 scanf("%d", &T); 60 while (T--) 61 { 62 scanf("%d", &n); 63 for (int i = 0; i <= n; i++) 64 p[i] = i; 65 66 for (int i = 0; i < n; i++) 67 scanf("%d%d", &x[i], &y[i]); 68 cnt = 0; 69 for (int i = 0; i < n; i++) 70 for (int j = i+1; j < n; j++) 71 { 72 double len=cacl(x[i], y[i], x[j], y[j]); 73 if (len >= 10 && len <= 1000) 74 { 75 edge[cnt].u = i; 76 edge[cnt].v = j; 77 edge[cnt].dist = len; 78 cnt++; 79 } 80 } 81 sort(edge, edge + cnt, cmp); 82 ans = 0; 83 Kruskal(); 84 if (num == n - 1) printf("%.1f\n", ans); 85 else printf("oh!\n"); 86 } 87 }
原文：http://www.cnblogs.com/zyb993963526/p/6392018.html