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

我的为什么老WA? 好心人看看。我剪枝了一下, 难道是这问题?

Posted by test_acm at 2008-09-16 21:19:12 on Problem 2236
/*
 * poj 2236 彻底的自己编一个UFS看? 
 */

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

#define N 1008
//#define K 300008

struct _node{
       int dx;
       int dy;
       }node[N];

int rank[N]={0}, p[N], visit[N] = {0};

int find( int x ) {
    if( x==p[x] )
        return p[x];
    else
        return find( p[x] );
    }
void merge( int root1, int root2 ) {
     int x=find( root1 );
     int y=find( root2 );
     if( x==y )
         return ;
     if( rank[x]>rank[y] )
         p[y] = x;
     else{
          p[x] = y;
          if( rank[x]==rank[y] )
              rank[y]++;
          }
     }


bool cmp( const _node a, const _node b ) {
     if( a.dx != b.dx )
         return a.dx<b.dx;
     else
         return a.dy<b.dy;
     }

int main() {
    //freopen( "c:\\in.txt" , "r", stdin );
    //freopen( "c:\\out.txt" , "w", stdout );
    
    double temp1, temp2, temp3, temp4, tmp;
    int n, d;
    int i, j, k;
    int x, y, z;
    char c;
    
    scanf( "%d %d", &n, &d );
    for( i=1; i<=n; i++ )
         p[i] = i;
    for( i=1; i<=n; i++ ) {
         scanf( "%d %d", &node[i].dx, &node[i].dy );
         }
    sort( &node[1], &node[n]+1, cmp );
    
    getchar();  // 
    while( scanf( "%c", &c )!=EOF ) {
           if( c=='O' ) {
               scanf( "%d", &z );
               getchar();//
               visit[z] = 1;  
               k=node[z].dx-d;  //这个地方开始有问题!!!
               if( k<0 )
                   i=1;
                   
               else {
                   for( i=z; i>0; i-- ) {
                        if( node[i].dx<k )
                            break;
                        }
                    }
                    
               for( ; node[i].dx<=(z+d); i++ ) {
                    if( visit[i] ) {
                        
                        temp1=( node[i].dx - node[z].dx );
                        temp2=( node[i].dy - node[z].dy );
                        temp3 = temp1*temp1;
                        temp4 = temp2*temp2;
                        tmp = temp3 + temp4;
                        if( tmp<=d ) {
                            merge( i, z );
                            }
                        }       
                    }
               
               }
           else if( c=='S' ) {
                scanf( "%d %d", &x, &y );
                getchar();
                if( find(x) == find(y) )
                    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