题意:
有 n 台电脑坏了,两台电脑之间超过距离 d 就无法直接通信。
但是可以借助另外的电脑进行间接通信。
(1 <= n <= 1001, 0 <= d <= 20000)
电脑编号从 1 到 n
接下来的 n 行,每行包含两个整数 xi, yi (0 <= xi, yi <= 10000),表示第 i 台电脑的坐标。
从第 (N+1) 行到输入结束,是逐一执行的操作,每行包含一个操作,格式是以下两者之一:
1. "O p" (1 <= p <= N),表示维护电脑 p 。
2. "S p q" (1 <= p, q <= N),表示测试电脑 p 和 q 是否能够通信。
问所有的测试操作中,可以通信的测试个数。
分析:
注意时间限制是10秒。。。。
既然如此,就简单了。
每维护一个电脑,就让它和所有已经维护过的电脑进行比较,
如果距离够,就用并查集合并。
对于每一次的测试操作,查找p q 的根节点,如果相同,说明可以进行通信,
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1010;
int d, r[MAXN];
int F[MAXN];
struct Node
{
double x, y;
bool f;
}a[MAXN];
void init(int n)
{
for (int i = 1; i <= n; i++)
r[i] = i, a[i].f = false;
}
int Find(int x)
{
return x == r[x] ? x : r[x] = Find(r[x]);
}
bool Join(int p, int q)
{
int rp = Find(p);
int rq = Find(q);
double D = (a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y);
D = sqrt(D);
if (rp != rq && D <= d) {
r[rp] = rq;
return true;
}
return false;
}
int main()
{
char c[2];
int n, p, q, len = 0;
cin >> n >> d;
init(n);
for (int i = 1; i <= n; i++)
scanf("%lf %lf", &a[i].x, &a[i].y);
while (scanf("%s %d", &c, &p)!=EOF)
{
if (c[0] == 'S')
{ // 测试
scanf("%d", &q);
if (!a[p].f || !a[q].f || Find(p)!=Find(q))
cout << "FAIL" << endl;
else
cout << "SUCCESS" << endl;
}
else
{
a[p].f = true;
F[len++] = p;
for (int i = 0; i < len-1; i++)
Join(F[i],p);
}
}
return 0;
}
Comments | NOTHING