10034 - Freckles 克鲁斯克尔最小生成树！～
生活随笔
收集整理的這篇文章主要介紹了
10034 - Freckles 克鲁斯克尔最小生成树！～
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1 /*
2 10034 - Freckles
3 克魯斯克爾最小生成樹！～
4 */
5 #include<iostream>
6 #include<cstdio>
7 #include<cmath>
8 #include<algorithm>
9 using namespace std;
10
11 struct node{
12 double x, y;
13 };
14
15 struct tree{
16 int u, v;
17 double d;
18 };
19
20 node nd[105];
21 int f[105];
22 tree tt[5010];
23
24 bool cmp(tree a, tree b){
25 return a.d < b.d;
26 }
27
28 int getFather(int x){
29 return x==f[x] ? x : f[x]=getFather(f[x]);
30 }
31
32 int Union(int a, int b){
33 int fa=getFather(a), fb=getFather(b);
34 if(fa!=fb){
35 f[fa]=fb;
36 return 1;
37 }
38 return 0;
39 }
40
41 int main(){
42 int t;
43 cin>>t;
44 while(t--){
45 int n;
46 cin>>n;
47 for(int i=1; i<=n; ++i){
48 cin>>nd[i].x>>nd[i].y;
49 f[i]=i;
50 }
51 int cnt=0;
52 for(int i=1; i<n; ++i)
53 for(int j=i+1; j<=n; ++j){
54 tt[cnt].u=i;
55 tt[cnt].v=j;
56 tt[cnt++].d=sqrt((nd[i].x-nd[j].x)*(nd[i].x-nd[j].x) + (nd[i].y-nd[j].y)*(nd[i].y-nd[j].y));
57 }
58 sort(tt, tt+cnt, cmp);
59 double sum=0.0;
60 for(int i=0; i<cnt; ++i){
61 if(Union(tt[i].u, tt[i].v))
62 sum+=tt[i].d;
63 }
64 printf("%.2lf\n", sum);
65 if(t) printf("\n");
66 }
67 }
?
轉載于:https://www.cnblogs.com/hujunzheng/p/3898428.html
總結
以上是生活随笔為你收集整理的10034 - Freckles 克鲁斯克尔最小生成树！～的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 清明节游戏服务器维护,清明节游戏活动【4
- 下一篇： 消费电子概念股龙头 机构们都非常看好