POJ2236 Wireless Network 并查集好题

浏览数：23 / 时间：2015年06月09日

　　　　　　　　　　Wireless Network

Description

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to work again. Because of the hardware restricts, each computer can only directly communicate with the computers that are not farther than d meters from it. But every computer can be regarded as the intermediary of the communication between two other computers, that is to say computer A and computer B can communicate if computer A and computer B can communicate directly or there is a computer C that can communicate with both A and B.

In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations.

Input

The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 <= xi, yi <= 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats:
1. "O p" (1 <= p <= N), which means repairing computer p.
2. "S p q" (1 <= p, q <= N), which means testing whether computer p and q can communicate.

The input will not exceed 300000 lines.

Output

For each Testing operation, print "SUCCESS" if the two computers can communicate, or "FAIL" if not.

Sample Input

Sample Output

FAIL
SUCCESS


题意：现在有n个电脑，按1开始编号，规定2个电脑可以直接通讯的条件：
　　　1.2个电脑都有维修过
　　　2.2个电脑的距离<=d
　　　当然，2个电脑也可以通过其他电脑间接联系

现在给出了n，d，
然后给出n台电脑的坐标(2维)，然后再给出操作：
O a   ：维修电脑a
S a b ：test电脑a和b是否可以连接

思路：
先算好dis[i][j] 表示i与j的距离(这个要先预处理好，不然等下会重复计算很多次，会tle)
O a   则vis[a]=true  然后遍历一遍，把vis[i]==true&&dis[a][i]<=d  的点i 和a 合并
S a b   若a和b的祖先节点相同，则SUCCESS，否则FAIL

学到了，先对数据进行预处理。

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 
 5 const int maxn=1005;
 6 double dis[maxn][maxn];
 7 int father[maxn];
 8 bool vis[maxn];
 9 int n,d;
10 struct Point
11 {
12     int x,y;
13 }point[maxn];
14 
15 void init_distance()
16 {
17     for(int i=1;i<=n;i++)
18         for(int j=1;j<=n;j++)
19          dis[i][j]=sqrt((long double)(point[i].x-point[j].x)
20 *(point[i].x-point[j].x)+(long double)(point[i].y-point[j].y)*(point[i].y-point[j].y));
21 }
22 
23 void init()
24 {
25     for(int i=1;i<=n;i++)
26     {
27         father[i]=i;
28         vis[i]=false;
29     }
30 }
31 
32 int find_set(int x)
33 {
34     if(father[x]==x)
35         return x;
36     else
37         return father[x]=find_set(father[x]);
38 }
39 
40 void union_set(int x,int y)
41 {
42     int fax=find_set(x);
43     int fay=find_set(y);
44     if(fax==fay)
45         return ;
46     father[fax]=fay;
47 }
48 
49 int main()
50 {
51     scanf("%d%d",&n,&d);
52     for(int i=1;i<=n;i++)
53         scanf("%d%d",&point[i].x,&point[i].y);
54 
55     init();
56     init_distance();
57     char str[3];
58     int a,b;
59     while(scanf("%s",&str)!=EOF)
60     {
61         if(str[0]==‘O‘)
62         {
63             scanf("%d",&a);
64             vis[a]=true;
65             for(int i=1;i<=n;i++)
66             {
67                 if(vis[i]&&dis[i][a]<=d)
68                 {
69                     union_set(i,a);
70                 }
71             }
72         }
73         else{
74             scanf("%d%d",&a,&b);
75             if(find_set(a)==find_set(b))
76                 printf("SUCCESS\n");
77             else
78                 printf("FAIL\n");
79         }
80     }
81     return 0;
82 }