Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

这题的复杂度是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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator