题目大意：就是地震后，所有的电脑都坏了，现在可以修复，而且要重新连成一个网络，两台电脑之间最大连接距离为D，两台电脑可以有中继电脑，按O修复电脑，按S测试两台电脑是否有链接，如果有就输出SUCCESS，不行就FAIL
一看到电脑，我就联想到了查并集，这一题也不例外，我们维护在距离内的查并集就可以了，具体思路不难，每一次修复都扫描所有的节点看能否连接即可
#include <iostream>
#include <functional>
#include <algorithm>
#include <math.h>
#define MAX 1004 using namespace std;
typedef int Position;
typedef struct _set
{
int x;
int y;
}Point; static Point Comp[MAX];
static Position Set[MAX];
static bool used[MAX];
static int max_dist; Position Find(Position);
void Unite_Set(Position, Position);
void Repaired(const int, Position);
void Test(Position, Position);
double Dist_Cal(Position, Position); int main(void)
{
int n, tmp_p, tmp_x, tmp_y;
char choice;
while (~scanf("%d%d", &n, &max_dist))
{
memset(Set, -, sizeof(Set));
memset(used, , sizeof(used));
for (int i = ; i <= n; i++)
scanf("%d%d", &Comp[i].x, &Comp[i].y);
getchar();
while (~scanf("%c", &choice))
{
if (choice == 'O')
{
scanf("%d", &tmp_p);
Repaired(n, tmp_p);
}
else
{
scanf("%d%d", &tmp_x, &tmp_y);
Test(tmp_x, tmp_y);
}
getchar();
}
}
return ;
} double Dist_Cal(Position i, Position j)
{
return sqrt((double)((Comp[i].x - Comp[j].x)*(Comp[i].x - Comp[j].x)) +
(double)((Comp[i].y - Comp[j].y)*(Comp[i].y - Comp[j].y)));
} void Unite_Set(Position x, Position y)
{
Position px, py;
px = Find(x); py = Find(y);
if (px != py)
{
if (Set[px] < Set[py])//按大小求并
{
Set[px] += Set[py];
Set[py] = px;
}
else
{
Set[py] += Set[px];
Set[px] = py;
}
}
} Position Find(Position x)
{
if (Set[x] < )
return x;
else return Set[x] = Find(Set[x]);
} void Repaired(const int n, Position x)
{
used[x] = ;
for (int i = ; i <= n; i++)
{
if (i == x || !used[i]) continue;
if (Dist_Cal(x, i) <= (double)max_dist)
Unite_Set(x, i);
}
} void Test(Position x, Position y)
{
Position px, py;
px = Find(x);
py = Find(y); if (px == py) puts("SUCCESS");
else puts("FAIL");
}