poj-2236 Wireless Network （基础并查集）

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

http://poj.org/problem?id=2236

由于发生了地震，有关组织组把一圈电脑一个无线网，但是由于余震的破坏，所有的电脑都被损坏，随着电脑一个个被修好，无线网也逐步恢复工作，但是由于硬件的限制，一台电脑和另一台电脑能够相连当他们之间的距离小于d，或者还有一台电脑当中介，分别与两台电脑相连。

在修复的过程中，工作者会有两种操作，修复电脑和询问电脑a和电脑b是否相连。当询问的时候输出答案。

因为输入数据很大，需要快速判断电脑a和电脑b相连，所以自然想到用并查集。

初始时候全部电脑都是损坏的，那么每修复一次，就需要把与当前电脑距离小于d并且已经修复的电脑连接起来，询问的时候直接判断即可。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 1010;
 6 struct node
 7 {
 8     int x,y;
 9 }p[maxn];
10 int par[maxn],flag[maxn];  //作为是否修复的标记
11 int n;
12 double dis[maxn][maxn];  //存储两点之间的距离
13 double d;
14 void init()
15 {
16     for(int i=1;i<=n;i++) par[i]=i;
17 }
18 
19 int find(int x)
20 {
21     return x==par[x]?x:par[x]=find(par[x]);
22 }
23 
24 void unite(int x,int y)
25 {
26     x=find(x);
27     y=find(y);
28     if(x!=y)
29         par[x]=y;
30 }
31 
32 void distance(int a,int b)
33 {
34     dis[a][b]=dis[b][a]=sqrt(1.0*(p[a].x-p[b].x)*(p[a].x-p[b].x)+1.0*(p[a].y-p[b].y)*(p[a].y-p[b].y));
35 }
36 
37 void solve(int x)
38 {
39     for(int i=1;i<=n;i++)
40     {
41         if(i!=x&&flag[i]&&dis[x][i]<=d)
42             unite(x,i);
43     }
44 }
45 
46 int main()
47 {
48    //freopen("a.txt","r",stdin);
49     scanf("%d%lf",&n,&d);
50     init();
51     memset(flag,0,sizeof(flag));
52     memset(dis,0,sizeof(dis));
53     for(int i=1;i<=n;i++)
54         scanf("%d%d",&p[i].x,&p[i].y);
55     for(int i=1;i<=n;i++)   //预处理所有两点之间的距离
56         for(int j=i+1;j<=n;j++)
57         distance(i,j);
58     char s[2];
59     int a,b;
60     while(~scanf("%s",s))
61     {
62         if(s[0]==‘O‘)
63         {
64             scanf("%d",&a);
65             flag[a]=1;
66             solve(a);
67         }
68         else if(s[0]==‘S‘)
69         {
70             scanf("%d%d",&a,&b);
71             if(find(a)==find(b)) printf("SUCCESS\n");
72             else printf("FAIL\n");
73         }
74     }
75     return 0;
76 }