#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>

double DTABLE[ 1002 ][ 1002 ];

 
using namespace std;
int parent[ 1002 ];
int status[ 1002 ];
int x[ 1002 ];
int y[ 1002 ];

int Find( int i )
{
	int j = i;
	while( parent[ j ] > 0 )	j = parent[ j ];
	if( i == j ) return j; //待查节点为根节点
	while( parent[ parent[ i ] ] > 0 )
	{//压缩路径 并更新up
		int k = i;
		parent[ i ] = j;
		i = parent[ k ];
	}
	return j;
}
//
//
void Union( int L, int R )
{
	if( parent[ L ] < parent[ R ] )
	{
		parent[ L ] += parent[ R ];
		parent[ R ] = L;
	}
	else
	{
		parent[ R ] += parent[ L ];
		parent[ L ] = R;
	}
}//Union

int main()
{
	freopen( "F:\\ACM\\Test_Data\\pku2236.in", "r", stdin );
	freopen( "F:\\ACM\\Test_Data\\pku2236.out", "w", stdout );
//	UnionFind uf( 1002 );
	int N, D;
	double fD;
	char order[ 2 ];
	int i, j;
	int id, pc1, pc2;
	scanf( "%d%d", &N, &D );
	fD = D;
	for( i = 1; i <= N; ++i )
	{
		scanf( "%d%d", &x[ i ], &y[ i ] );
	}
	memset( parent, -1, 1002*sizeof( int ) );
	memset( status, 0, 1002*sizeof( int ) );
	memset( DTABLE, 0, 1002*1002*sizeof( double ) );
	while( scanf( "%s", order ) != EOF )
	{
		if( order[ 0 ] == 'O' )
		{
			scanf( "%d", &id );
			int cx = x[ id ];
			int cy = y[ id ];
			status[ id ] = 1;
			for( i = 1; i<=N; ++i )
			{
				if( i != id && status[ i ] == 1 )
				{
					int idroot = Find( id );
					int iroot = Find( i );
					if( idroot == iroot ) continue;
					if( DTABLE[ i ][ id ] == 0 )
					{
						DTABLE[ i ][ id ] = hypot(cx - x[ i ], cy - y[ i ]);
						DTABLE[ id ][ i ] = DTABLE[ i ][ id ];
					}
					if( DTABLE[ i ][ id ] <= fD )
						Union( idroot, iroot );
				}
			}
		}
		else
		{
			scanf( "%d%d\n", &pc1, &pc2 );
			if( Find( pc1 ) == Find( pc2 ) )
				printf( "SUCCESS\n" );
			else
				printf( "FAIL\n" );
		}//else
	}//while
	return 0;
}

• Re:大牛帮下 看看是什么导致效率低下？ (40) andy_lee 2007-12-11 22:52:07
• Re:大牛帮下 看看是什么导致效率低下？ (30) andy_lee 2007-12-11 23:26:48