首页 > 代码库 > hdu1162 Eddy's picture 基础最小生成树
hdu1162 Eddy's picture 基础最小生成树
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 #include <string> 6 using namespace std; 7 8 int n, m; 9 int f[510]; 10 11 struct node 12 { 13 int u, v; 14 double w; 15 }map[10010]; 16 17 int getf(int a) 18 { 19 if (f[a] == a) 20 { 21 return a; 22 } 23 24 f[a] = getf(f[a]); 25 return f[a]; 26 } 27 28 void merge(int a, int b) 29 { 30 int x = getf(a); 31 int y = getf(b); 32 33 if (x != y) 34 f[y] = x; 35 } 36 37 38 void init() 39 { 40 for (int i = 1; i <= n; i++) 41 f[i] = i; 42 } 43 44 bool cmp(node a, node b) 45 { 46 return a.w < b.w; 47 } 48 49 double kura() 50 { 51 double res = 0; 52 sort(map, map + m, cmp); 53 54 for (int i = 0; i < m; i++) 55 { 56 if (getf(map[i].u) != getf(map[i].v)) 57 { 58 merge(map[i].u, map[i].v); 59 res += map[i].w; 60 } 61 } 62 return res; 63 } 64 65 double a[102][2]; 66 67 68 int main() 69 { 70 while (scanf("%d", &n) != EOF) 71 { 72 m = n*(n - 1); 73 for (int i = 1; i <= n; i++) 74 scanf("%lf %lf", &a[i][0], &a[i][1]); 75 76 int k = 0; 77 for (int i = 1; i <= n; i++) 78 { 79 for (int j = i + 1; j <= n; j++) 80 { 81 map[k].u = i; 82 map[k].v = j; 83 map[k].w = sqrt(abs(pow(a[j][0] - a[i][0], 2) + pow(a[j][1] - a[i][1], 2))); 84 k++; 85 } 86 } 87 init(); 88 printf("%.2lf\n", kura()); 89 } 90 91 return 0; 92 }
hdu1162 Eddy's picture 基础最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。