DisJSet:Wireless Network(POJ 2236)

　　　　　　　　　　　　　　　　无线电网络

　　题目大意：就是地震后，所有的电脑都坏了，现在可以修复，而且要重新连成一个网络，两台电脑之间最大连接距离为D，两台电脑可以有中继电脑，按O修复电脑，按S测试两台电脑是否有链接，如果有就输出SUCCESS，不行就FAIL

　　一看到电脑，我就联想到了查并集，这一题也不例外，我们维护在距离内的查并集就可以了，具体思路不难，每一次修复都扫描所有的节点看能否连接即可

  1 #include <iostream>
  2 #include <functional>
  3 #include <algorithm>
  4 #include <math.h>
  5 #define MAX 1004
  6 
  7 using namespace std;
  8 typedef int Position;
  9 typedef struct _set
 10 {
 11     int x;
 12     int y;
 13 }Point;
 14 
 15 static Point Comp[MAX];
 16 static Position Set[MAX];
 17 static bool used[MAX];
 18 static int max_dist;
 19 
 20 Position Find(Position);
 21 void Unite_Set(Position, Position);
 22 void Repaired(const int, Position);
 23 void Test(Position, Position);
 24 double Dist_Cal(Position, Position);
 25 
 26 int main(void)
 27 {
 28     int n, tmp_p, tmp_x, tmp_y;
 29     char choice;
 30     while (~scanf("%d%d", &n, &max_dist))
 31     {
 32         memset(Set, -1, sizeof(Set));
 33         memset(used, 0, sizeof(used));
 34         for (int i = 1; i <= n; i++)
 35             scanf("%d%d", &Comp[i].x, &Comp[i].y);
 36         getchar();
 37         while (~scanf("%c", &choice))
 38         {
 39             if (choice == 'O')
 40             {
 41                 scanf("%d", &tmp_p);
 42                 Repaired(n, tmp_p);
 43             }
 44             else
 45             {
 46                 scanf("%d%d", &tmp_x, &tmp_y);
 47                 Test(tmp_x, tmp_y);
 48             }
 49             getchar();
 50         }
 51     }
 52     return 0;
 53 }
 54 
 55 double Dist_Cal(Position i, Position j)
 56 {
 57     return sqrt((double)((Comp[i].x - Comp[j].x)*(Comp[i].x - Comp[j].x)) + 
 58         (double)((Comp[i].y - Comp[j].y)*(Comp[i].y - Comp[j].y)));
 59 }
 60 
 61 void Unite_Set(Position x, Position y)
 62 {
 63     Position px, py;
 64     px = Find(x); py = Find(y);
 65     if (px != py)
 66     {
 67         if (Set[px] < Set[py])//按大小求并
 68         {
 69             Set[px] += Set[py];
 70             Set[py] = px;
 71         }
 72         else
 73         {
 74             Set[py] += Set[px];
 75             Set[px] = py;
 76         }
 77     }
 78 }
 79 
 80 Position Find(Position x)
 81 {
 82     if (Set[x] < 0)
 83         return x;
 84     else return Set[x] = Find(Set[x]);
 85 }
 86 
 87 void Repaired(const int n, Position x)
 88 {
 89     used[x] = 1;
 90     for (int i = 1; i <= n; i++)
 91     {
 92         if (i == x || !used[i]) continue;
 93         if (Dist_Cal(x, i) <= (double)max_dist)
 94             Unite_Set(x, i);
 95     }
 96 }
 97 
 98 void Test(Position x, Position y)
 99 {
100     Position px, py;
101     px = Find(x);
102     py = Find(y);
103 
104     if (px == py) puts("SUCCESS");
105     else puts("FAIL");
106 }