首页 > > 程序设计 > C/C++ >

POJ 2236 Wireless Network 第一次做并查集，第…

2018-06-17 23:56:15来源：未知阅读 ()

题意是判断两台电脑是否能通讯，两台修好的电脑距离在指定距离内可直接通讯，且两台修好的电脑能通过一台修好的电脑间接通讯。代码如下：

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

int father[1005];
struct Coord //电脑坐标
{
    int x;
    int y;
} coo[1005];
struct Repair //已修复好的电脑的坐标和编号
{
    int x;
    int y;
    int numb;
} rep[1005];

int Find_fath(int x) //并查集寻找父亲
{
    if (x != father[x])
        father[x] = Find_fath(father[x]); //压缩返回路径
    return father[x];
}
void Union(int x,int y) //并查集父亲合并
{
    x=Find_fath(x);
    y=Find_fath(y);
    if(x!=y)
        father[y]=x;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n,d;
    int num_rep=0; //修复电脑的数量
    char oper; //对电脑的操作
    cin>>n>>d;
    for(int i=1; i<=n; i++)
        scanf("%d%d",&coo[i].x,&coo[i].y);
    for(int i=1; i<=n; i++)
        father[i]=i;        //初始化父亲为自己
    getchar();
    while(scanf("%c",&oper)!=EOF)
    {
        if(oper=='O')
        {
            int numb;
            scanf("%d",&numb);
            rep[num_rep].x=coo[numb].x;
            rep[num_rep].y=coo[numb].y;
            rep[num_rep].numb=numb;
            for(int i=0; i<num_rep; i++)
            {
                if(num_rep==0)break;
                int a,b;
                a=rep[i].x-rep[num_rep].x;
                b=rep[i].y-rep[num_rep].y;
                if(a*a+b*b<=d*d)
                    Union(rep[i].numb,rep[num_rep].numb);
            }
            num_rep++;
        }
        else
        {
            int num1,num2;
            scanf("%d%d",&num1,&num2);
            if(Find_fath(num1)==Find_fath(num2))
                printf("SUCCESS\n");
            else
                printf("FAIL\n");
        }
        getchar();
    }
    return 0;
}