01、实例分析：人工湖公路

问题描述:

东南亚发生了一场地震,ICPC组织通过计算机建立的无线网络遭到毁灭性的影响——网络中所有的计算机都损坏了。在陆续维修计算机之后，无线网络又逐渐开始运作。由于硬件的制约，每两台计算机只有保持不超过d米的距离，才可以直接进行通信。但是每台计算机又可以作为其他两台计算机通信的中介点，也就是说，假设A计算机与B计算机不在能直接通信的范围内，但是它们可以通过同时能与A和B计算机通信的C计算机建立间接通信关系。

在维修过程中，维修者可以进行两种操作: 维修一台计算机或者检测两台计算机之间是否能够通信。你的任务就是解答每一次的检测操作。

输入:

第一行包含两个整数N和d(1≤N≤1001,0≤d≤20000)。N表示计算机的数量，计算机编号从1开始到N，d为两台能直接通信的计算机所需保持距离的最大值。在接下来的N行，每行包含两个整数xi,yi(0≤xi,yi≤10000),表示N台计算机的坐标。接下来的一系列的输入都表示维修者的操作，每种操作都是以下两种中的一种。

1. "O p" (1≤p≤N),表示维修第p台计算机。

2. "S p q" (1≤p,q≤N), 表示检测p与q计算机是否能够通信。

输入不超过300000 行。

输出:

对于每组检测操作，若两台计算机能进行通信，则输出SUCCESS，否则输出FAIL。

输入样例:

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4

输出样例:

FAIL
SUCCESS

解题思路:

(1) 本题的基本解题方法是通过并查集划分集合，根据每对点（每对计算机）的从属关系判断点（计算机）是否连通（通信）。

(2) 需根据计算机的通信范围确定每对计算机是否可以直接通信。

(3) 需注意的是，必须保证可以进行通信的每对计算机是完好无损的。

本题只要能正确建图（建立计算机间是否通信的关系），再通过并查集的知识就可以解题了，注意初始时每台计算机都是损坏的。解题步骤如下。

(1) 输入每个点的坐标后，首先根据计算机的通信范围建立每对计算机的连通关系。

(2) 当输入的操作为维修时，就将本台计算机标记为完好的，并将其与所有与其可以通信的且完好的计算机进行并操作，那么可通信的计算机都在同一棵树中，具有相同的根结点。

(3) 当输入的操作为询问时，若两台计算机具有相同的根结点，则可通信，否则不可通信。

参考程序:

#include<stdlib.h>
#include<math.h>
int map[1005][1005];
int mul(int x)
//求平方数的函数
return x *x;
int f[1005];int find(int x)
if(f[x]!=x)f[x]=find(f[x]);return f[x];
void make(int a,int b)
int fl=find(a);
int f2=find(b);if(f1!=f2)
f[f2]=f1;
void check(int a,int b)
//检验 a 与 b 是否连通并输出的函数
int fl=find(a);int f2=find(b);if(fl==f2)
printf("SUCCESS\n");return ;
printf("FAIL\n");
int main()
int n,flag[1005];
//flag 数组用于标记计算机是否完好
double d;
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag)) ;
scanf("号d号lf",&n,&d) ;
int x[1005],y[1005],i,j,k;for(i=1;i<=n;i++)
scanf("号d%d",&x[i],&y[il);for(i=l;i<=n;i++)
f[i]=i;for(i=1;i<n;i++)
//用两层 for 循环对可直接通信的两台计算机进行标记
for(j=i+1;j<=n;j++)if(sqrt((double) (mul(x[i]-x[j]) +mul(y[il-y[j]) ))<=d)
map[i][j]=1;
map[j][i]=1;
char s[5];
int a,b;
while(scanf("s",s)!=EOF)
if(strcmp(s,"O")== 0)
scanf("d",&a);flag[a]=1;for(i=l;i<=n;i++)if(map[illal&&flag[i])//将可直接通信的并且完好的计算机合并为同一个集合make(a,i);
else
scanf("各d号d",&a,&b);check(a,b);
//判断并输出结果