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

麻烦帮忙看下,这题不就是并查集吗,why TLE?

Posted by tzy at 2008-02-24 14:28:06 on Problem 2236
#include<iostream>

using namespace std;
const int N = 1001;
bool flag[N][N];
int n,d;
bool used[N];
struct POINT
{
	int x,y;
};
POINT point[N];


struct COMPUTER
{
	int parent;
	int rank;
};
COMPUTER computer[N];

void initial(int n)
{
	int i;
	for (i=1;i<=n;i++)
	{
		computer[i].parent = i;
		computer[i].rank = 0;
	}
}


int find_set(int x)
{
	int p = x;
	while (computer[x].parent != x)
	{
		x = computer[x].parent;
	}
	while (computer[p].parent != x)
	{
		computer[p].parent = x;
		p = computer[p].parent;
	}
	return x;
}

void union_set(int x,int y)
{
	x = find_set(x);
	y = find_set(y);
	if(computer[x].rank > computer[y].rank)
	{
		computer[y].parent = x;
	}
	else
	{
		computer[x].parent = y;
		if(computer[x].rank == computer[y].rank)
			computer[y].rank++;
	}
}

int main()
{
	int i,j,dis,p,q;
	char ch[2];
	scanf("%d%d",&n,&d);
	initial(n);
	d = d*d;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&point[i].x,&point[i].y);
	}
	memset(flag,false,sizeof(flag));
	memset(used,false,sizeof(used));
	for(i=1;i<=n;i++)
	{
		for (j=i+1;j<=n;j++)
		{
			dis = (point[i].x - point[j].x)*(point[i].x - point[j].x)+(point[i].y - point[j].y)*(point[i].y - point[j].y);
			if( dis <= d )
				flag[i][j] = flag[j][i] = true;
		}
	}
	while (1)
	{
		/*
		getchar();
		if(scanf("%c",ch)!=1)
		break;*/
		while(scanf("%s",ch) != EOF )
		{

			if(ch[0] == 'O')
			{
				scanf("%d",&p);
				used[p] = true;
				for(i=1;i<=n;i++)
				{
					if(i!=p && used[i] && flag[p][i])
					{
						union_set(p,i);
					}
				}
			}
			else
			{
				scanf("%d%d",&p,&q);
				p = find_set(p);
				q = find_set(q);
				if(p==q)
					printf("SUCCESS\n");
				else
					printf("FAIL\n");
			}
		}
	}
	return 0;
}

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