hdu4463 Outlets 最小生成树

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4463
很裸的一道题目，稍微处理一下输入即可
代码：
  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 #define maxn 60
  9 int n;
 10 double sumweight;
 11 int tol;
 12 int cnt;
 13 int p,q;
 14 class node
 15 {
 16   public:
 17   int from;
 18   int to;
 19   double w;
 20 };
 21 class point
 22 {
 23    public:
 24    int x;
 25    int y;
 26 };
 27 point address[maxn];
 28 node edge[maxn*maxn];
 29 int  parent[maxn*maxn];
 30 double dis(point a,point b)
 31 {
 32     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 33 }
 34 void addEdge(int u,int v)
 35 {
 36    edge[tol].from=u;
 37    edge[tol].to=v;
 38    edge[tol].w=dis(address[u],address[v]);
 39    if((u==p && v==q)||(u==q && v==p))
 40    edge[tol].w=0;
 41    tol++;
 42 }
 43 void UFset()
 44 {
 45    for(int i=0;i<maxn*maxn;i++)
 46        parent[i]=-1;
 47 }
 48 int Find(int x)
 49 {
 50    int s;
 51     for(s=x;parent[s]>=0;s=parent[s]);//我总是把parent[s]>=0 写为s>=0;
 52     while(s!=x)
 53     {
 54         int tmp=parent[x];
 55         parent[x]=s;
 56         x=tmp;
 57     }
 58 
 59    return s;
 60 }
 61 void Union(int u,int v)
 62 {
 63     int r1=Find(u);
 64     int r2=Find(v);
 65     int tmp=parent[r1]+parent[r2];
 66     if(parent[r1]>parent[r2])
 67     {
 68         parent[r1]=r2;
 69         parent[r2]=tmp;
 70     }
 71     else
 72     {
 73         parent[r2]=r1;
 74         parent[r1]=tmp;
 75     }
 76 }
 77 bool cmp(node a ,node b)
 78 {
 79      return a.w < b.w;
 80 }
 81 void Kruskal()
 82 {
 83     int u,v;
 84     UFset();
 85     cnt=0;
 86    for(int i=0;i<tol;i++)
 87    {
 88        u=edge[i].from;
 89        v=edge[i].to;
 90        if(Find(u)!= Find(v))
 91        {
 92             sumweight+=edge[i].w;
 93             cnt++;
 94             Union(u,v);
 95             if(cnt==n-1) break;
 96        }
 97    }
 98 
 99 }
100 int main()
101 {
102      while(scanf("%d",&n)&&n)
103      {
104         tol=0;
105 
106         scanf("%d%d",&p,&q);
107         int x,y;
108         for(int i=1;i<=n;i++)
109          {
110             scanf("%d%d",&x,&y);
111             address[i].x=x;
112             address[i].y=y;
113          }
114         for(int i=1;i<=n;i++)
115          for(int j=i+1;j<=n;j++)
116             {
117                addEdge(i,j);
118             }
119         sumweight=dis(address[p],address[q]);
120         sort(edge,edge+tol,cmp);
121         Kruskal();
122         printf("%.2f
",sumweight);
123         
124 
125 
126     }
127 
128 
129    return 0;
130 }