| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题的复杂度是O(N ^ 2 + M),因为修理操作最多执行N次,每次检测N - 1个计算机,剩下的只能是判断操作,每一次判断可以看作O( 1 )#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator