您现在的位置是:首页 > web开发 > Wireless Network 并查集

Wireless Network 并查集

web开发作者:dayu日期:4天前点击:2
2. "S p q" (1 <= p, q <= N), which means testing whether computer p and q can communicate.

The input will not exceed 300000 lines.

Output

For each Testing operation, print "SUCCESS" if the two computers can communicate, or "FAIL" 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

并查集,每修好一台电脑,枚举一遍其他n-1点,<=d且修好的合并。距离的判断稍坑。。斜方向需要算直线距离。

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int f[1005],xx[1005],yy[1005],re[1005];
double d;
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
void join(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy) f[fy]=fx;
}
int dis(int x,int i)
{
    double y;
    y=sqrt(abs(xx[x]-xx[i])*abs(xx[x]-xx[i])+abs(yy[x]-yy[i])*abs(yy[x]-yy[i]));
    if(d>=y) return 1;
    return 0;
}

int main()
{
    int n,x,y,i;
    char s[5];
    scanf("%d%lf",&n,&d);
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        xx[i]=x;
        yy[i]=y;
        f[i]=i;
    }
    getchar();
    while(~scanf("%s",s)){
        if(s[0]==O){
            scanf("%d",&x);
            re[x]=1;
            for(i=1;i<=n;i++){ 
                if(re[i]==1&&dis(x,i)){
                    join(x,i);
                } 
            }
        }
        else{
            scanf("%d%d",&x,&y);
            if(re[x]==1&&re[y]==1&&find(x)==find(y)) printf("SUCCESS\n");
            else printf("FAIL\n");
        }
        getchar();
    }
    return 0;
}

Wireless Network 并查集

原文地址:http://www.cnblogs.com/yzm10/p/7224147.html


下一篇       上一篇