poj 2253 Frogger

这道题我是用并查集处理的，将所有边排序，当生成树里出现第一个点，第二个点时（或第0点第1个点），结束并查集，输出已处理边里的最大值就可以了。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 #define MAXN 210
 5 int n,g,h,u[MAXN*MAXN],v[2*MAXN*MAXN],p[MAXN],r[2*MAXN*MAXN];
 6 double x[MAXN],y[MAXN],w[2*MAXN*MAXN],flag[2*MAXN*MAXN];
 7 
 8 int cmp(const void *_p, const void *_q)
 9 {
10     int *p = (int *)_p;
11     int *q = (int *)_q;
12     return w[*p]>w[*q] ? 1 : -1;
13 }
14 int find(int x2){return p[x2] == x2 ? x2 : p[x2] = find(p[x2]);}
15 void kruskal()
16 {
17     double ans = -1;
18     int ok1 = 0, ok2 = 0;
19     for(int i = 0; i < n; i ++) p[i] = i;
20     for(int i = 0; i < h; i ++) r[i] = i;
21     qsort(r,h,sizeof(r[0]),cmp);
22     g = 0;
23     for(int i = 0; i < h; i ++)
24     {
25         int e = r[i];
26         int x1 = find(u[e]), y1 = find(v[e]);
27         if(find(0) == find(1))break;
28         if(x1 != y1)
29         {
30             p[x1] = y1;
31             flag[g ++] = w[e];
32          }
33     }
34     for(int i = 0; i < g; i ++)
35     {
36         if(flag[i] > ans) ans = flag[i];
37     }
38     printf("Frog Distance = %.3f\n\n",ans);
39 }
40 void init()
41 {
42     int num = 1;
43     while(~scanf("%d",&n))
44     {
45         if(n == 0) break;
46         for(int i = 0; i < n; i ++)
47             scanf("%lf%lf",&x[i], &y[i]);
48         h = 0;
49         for(int i = 0; i < n; i ++)
50             for(int j = i+1; j < n; j ++)
51             {
52                 double dis = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
53                 u[h] = i, v[h] = j, w[h++] = dis;
54                 u[h] = j; v[h] = i, w[h++] = dis;
55             }
56             printf("Scenario #%d\n",num++);
57         kruskal();    
58     }    
59 }
60 
61 int main()
62 {
63     init();
64     return 0;
65 }