`
925695531
  • 浏览: 22192 次
  • 性别: Icon_minigender_1
文章分类
社区版块
存档分类
最新评论

poj2236解题报告

 
阅读更多

题意:有N个点;多条路;事先每个点都被摧毁;输入两个数字A,B代表这两个点有一条路,字符O和数字A,代表修复这个点;若输入S,A,B代表询问A,B是否连通;

题解:并查集

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;

const int MAXN = 1005 ;

struct type
{
    int x , y ;
} ;

type  Point[MAXN] ;

int   father[MAXN] ;
bool  vis[MAXN]    ;

int   find( int x )
{
    if( father[x] != x ) father[x] = find( father[x] ) ;
    return father[x] ;
}

void  Union( int a , int b )
{
    int  f1 = find( a ) ;
    int  f2 = find( b ) ;
    if( f1 != f2 ) father[f1] = f2 ;
}

int  length( type a , type b )
{
    int  len ;
    len = ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) ;
    return len ;
}

int  main()
{

    int   N , d ;
    char  ch    ;
    int   num   ;

    memset( vis , 0 , sizeof( vis ) ) ;
    for( int i = 0 ; i <= MAXN ; i ++ )
        father[i] = i ;

    cin >> N >> d ;
    for( int i = 1 ; i <= N ; i ++ )
        cin >> Point[i].x >> Point[i].y ;

    while( cin >> ch )
    {
        if( ch == 'O' )
        {
            cin >> num ;
            vis[num] = 1 ;
            for( int i = 1 ; i <= N ; i ++ )
            {
                if( i == num ) continue ;
                if( !vis[i]  ) continue ;
                if( length( Point[num] , Point[i] ) <= d * d )
                    Union( i , num ) ;
            }
        }
        else
        {
            int  a , b ;
            cin >> a >> b ;
            int  f1 = find( a ) ;
            int  f2 = find( b ) ;
            if( f1 == f2 ) cout << "SUCCESS" << endl ;
            else cout << "FAIL" << endl ;

        }
    }
    return 0 ;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics