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

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

新老客户大回馈,云服务器低至5折

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

#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;
}

不足之处,望多指点改正。转载请标明出处。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++程序实例唯一方案,窗口只打开一次,程序只打开一次

下一篇:隐式接口和编译期多态