Wireless ;Network

; ;<table ;align="center"> ; ;<tbody> ; ;<tr> ; ;<td>Time ;Limit: 10000MS</td> ; ;<td ;width="10px"> </td> ; ;<td>Memory ;Limit: 65536K</td> ; ;</tr> ; ;<tr> ; ;<td>Total ;Submissions: 24155</td> ; ;<td ;width="10px"> </td> ; ;<td>Accepted: 10045</td> ; ;</tr> ; ;</tbody> ; ;</table> ; ;

Description

An ;earthquake ;takes ;place ;in ;Southeast ;Asia. ;The ;ACM ;(Asia ;Cooperated ;Medical ;team) ;have ;set ;up ;a ;wireless ;network ;with ;the ;lap ;computers, ;but ;an ;unexpected ;aftershock ;attacked, ;all ;computers ;in ;the ;network ;were ;all ;broken. ;The ;computers ;are ;repaired ;one ;by ;one, ;and ;the ;network ;gradually ;began ;to ;work ;again. ;Because ;of ;the ;hardware ;restricts, ;each ;computer ;can ;only ;directly ;communicate ;with ;the ;computers ;that ;are ;not ;farther ;than ;d ;meters ;from ;it. ;But ;every ;computer ;can ;be ;regarded ;as ;the ;intermediary ;of ;the ;communication ;between ;two ;other ;computers, ;that ;is ;to ;say ;computer ;A ;and ;computer ;B ;can ;communicate ;if ;computer ;A ;and ;computer ;B ;can ;communicate ;directly ;or ;there ;is ;a ;computer ;C ;that ;can ;communicate ;with ;both ;A ;and ;B. In ;the ;process ;of ;repairing ;the ;network, ;workers ;can ;take ;two ;kinds ;of ;operations ;at ;every ;moment, ;repairing ;a ;computer, ;or ;testing ;if ;two ;computers ;can ;communicate. ;Your ;job ;is ;to ;answer ;all ;the ;testing ;operations.

Input

The ;first ;line ;contains ;two ;integers ;N ;and ;d ;(1 ;&lt;= ;N ;&lt;= ;1001, ;0 ;&lt;= ;d ;&lt;= ;20000). ;Here ;N ;is ;the ;number ;of ;computers, ;which ;are ;numbered ;from ;1 ;to ;N, ;and ;D ;is ;the ;maximum ;distance ;two ;computers ;can ;communicate ;directly. ;In ;the ;next ;N ;lines, ;each ;contains ;two ;integers ;xi, ;yi ;(0 ;&lt;= ;xi, ;yi ;&lt;= ;10000), ;which ;is ;the ;coordinate ;of ;N ;computers. ;From ;the ;(N+1)-th ;line ;to ;the ;end ;of ;input, ;there ;are ;operations, ;which ;are ;carried ;out ;one ;by ;one. ;Each ;line ;contains ;an ;operation ;in ;one ;of ;following ;two ;formats: 1. &quot;O ;p&quot; ;(1 ;&lt;= ;p ;&lt;= ;N), ;which ;means ;repairing ;computer ;p. 2. &quot;S ;p ;q&quot; ;(1 ;&lt;= ;p, ;q ;&lt;= ;N), ;which ;means ;testing ;whether ;computer ;p ;and ;q ;can ;communicate. The ;input ;will ;not ;exceed ;300000 ;lines.

Output

For ;each ;Testing ;operation, ;print ;&quot;SUCCESS&quot; ;if ;the ;two ;computers ;can ;communicate, ;or ;&quot;FAIL&quot; ;if ;not.

Sample ;Input

4 ;1 ; ;0 ;1 ; ;0 ;2 ; ;0 ;3 ; ;0 ;4 ; ;O ;1 ; ;O ;2 ; ;O ;4 ; ;S ;1 ;4 ; ;O ;3 ; ;S ;1 ;4

Sample ;Output

FAIL ; ;SUCCESS题目大意:将修好的电脑连通,随后询问俩电脑是否能接通

题目链接:http://poj.org/problem?id=2236

代码:

#include <iostream>
#include <cstring>
using namespace std;
struct ss
{
    int x,y;
}s[1010];
int map[1010][1010];
int vis[1010];
int f[1010];
int find(int n)
{
    if(n!=f[n])
    f[n]=find(f[n]);
    return f[n];
}
int main()
{ int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i].x>>s[i].y;
        map[i][i]=0;
        for(int j=i-1;j>0;j--)
        map[i][j]=map[j][i]=(s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y);
    }
    for(int i=1;i<=n;i++)
    f[i]=i;
    memset(vis,0,sizeof(vis));
    char a[10];
    int b,c;
    while(cin>>a)
    {
        if(a[0]=='O')
        {
            cin>>b;
            vis[b]=1;
            for(int i=1;i<=n;i++)
            {
                if(map[b][i]<=d*d&&i!=b&&vis[i])
                {
                    int a1=find(b);
                    int b1=find(i);
                    if(a1!=b1);
                    f[b1]=a1;
                }
            }
        }
        else
        {
            cin>>b>>c;
            if(vis[b]&&vis[c]&&find(b)==find(c))
            cout<<"SUCCESS"<<endl;
            else
            cout<<"FAIL"<<endl;
        }
    }

    return 0;
}