hdu 1875 最小生成树(kruskal)

  1 /*
  2 题意：中文题
  3 
  4 题解：赤裸裸的最小生成树
  5 */
  6 #include <cstdio>
  7 #include <cmath>
  8 #include <algorithm>
  9 
 10 const int MAXN = 109;
 11 const int MAXE = 10009;
 12 
 13 struct edge
 14 {
 15     int u, v;
 16     double w;
 17     bool vis;
 18 }E[MAXE];
 19 
 20 int set[MAXN];
 21 int N, EN, sum;
 22 
 23 void addedge(int u, int v, double w)
 24 {
 25     E[ EN ].u = u;
 26     E[ EN ].v = v;
 27     E[ EN ].w = w;
 28     E[ EN ].vis = false;
 29     EN++;
 30     return ;
 31 }
 32 
 33 void init()
 34 {    
 35     for (int i = 1; i <= N; i++) // 树的标号从1开始
 36         set[i] = i;
 37     return ;
 38 }
 39 
 40 int find(int x)
 41 {
 42     while (set[x] != x)
 43         x = set[x];
 44     return set[x];
 45 }
 46 
 47 bool cmp(edge a, edge b)
 48 {
 49     return a.w < b.w;
 50 }
 51 
 52 double kruskal()
 53 {
 54     int x, y;
 55     double ret;
 56     init();
 57     sum = 0;
 58     ret = 0;
 59     std::sort(E,E+EN,cmp);
 60     for (int i = 0; i < EN && sum < N - 1; i++)
 61     {
 62         x = find( E[i].u );
 63         y = find( E[i].v );
 64         if (x == y)
 65             continue;
 66         set[x] = set[y];
 67         E[i].vis = true;
 68         sum++;
 69         ret += E[i].w;
 70     }    
 71     return ret;
 72 }
 73 
 74 struct point
 75 {
 76     int x,y;
 77 }P[MAXN];
 78 
 79 int getdisSq(point a, point b)
 80 {
 81     return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
 82 }
 83 
 84 int main(void)
 85 {
 86     int t;
 87     scanf("%d",&t);
 88     while (t--)
 89     {
 90         scanf("%d",&N);
 91         for(int i=1; i<=N; i++)
 92             scanf("%d%d",&P[i].x,&P[i].y);
 93         EN = 0;
 94         for(int i=1; i<N; i++)
 95         {
 96             for(int j=i+1; j<=N; j++)
 97             {
 98                 int tmp = getdisSq(P[i],P[j]);
 99                 if (100 <= tmp && tmp <= 1000000)
100                     addedge(i,j,sqrt(1.0*tmp));
101             }
102         }
103         double ans = kruskal();
104         if (sum == N-1)
105             printf("%.1lf\n",100*ans);
106         else
107             printf("oh!\n");
108     }
109     return 0;
110 }