Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这题的复杂度是O(N ^ 2 + M)，因为修理操作最多执行N次，每次检测N - 1个计算机，剩下的只能是判断操作，每一次判断可以看作O( 1 )

Posted by a280920481 at 2018-11-28 00:09:02 on Problem 2236
```#include <iostream>
#include <math.h>
using namespace std;

struct Computer
{
bool repaired;//是否已被修复
int x;//横坐标
int y;//纵坐标
int father;//父节点
int depth;//树的深度
}com[1002];

void unite(int a, int b);//合并操作
int findfather(int a);//查询操作

double getdistance(const int & a, const int & b);//返回 a b 两个节点的距离

int main()
{

int N, d, p, q;//节点数 最大距离 p q
char ope;//操作类型

cin >> N >> d;

for (int i = 1; i <= N; i++)
{
cin >> com[i].x >> com[i].y;
com[i].father = i;//将每个节点的父节点初始化为自身
}

while (cin >> ope)
{
if (ope == 'O')
{
cin >> p;
for (int i = 1; i <= N; i++)
{
if (com[i].repaired)
{
if (getdistance(i, p) <= d)
{
unite(i, p);
}
}
}
com[p].repaired = true;
}
else
{
cin >> p >> q;
if (findfather(p) == findfather(q))
{
cout << "SUCCESS\n";
}
else
{
cout << "FAIL\n";
}
}
}

return 0;
}

void unite(int a, int b)
{
a = findfather(a);
b = findfather(b);
if (a != b)
{
if (com[a].depth == com[b].depth)
{
com[a].father = b;
com[b].depth++;
}
else if (com[a].depth > com[b].depth)
{
com[b].father = a;
}
else
{
com[a].father = b;
}
}
return;
}

int findfather(int a)
{
if (com[a].father == a)
{
return a;
}
else
{
return com[a].father = findfather(com[a].father);
}
}

double getdistance(const int & a, const int & b)
{
static int dx, dy;

dx = com[a].x - com[b].x;
dy = com[a].y - com[b].y;

return sqrt((double)(dx * dx + dy * dy));
}
```

Followed by: