poj2236-Wireless Network(并查集)

发布于 2019-08-07  749 次阅读


问题传送门:

题意:

有 n 台电脑坏了,两台电脑之间超过距离 d 就无法直接通信。
但是可以借助另外的电脑进行间接通信。  
(1 <= n <= 1001, 0 <= d <= 20000) 
电脑编号从 1 到 n
接下来的 n 行,每行包含两个整数 xi, yi (0 <= xi, yi <= 10000),表示第 i 台电脑的坐标。
从第 (N+1) 行到输入结束,是逐一执行的操作,每行包含一个操作,格式是以下两者之一: 
1. "O p" (1 <= p <= N),表示维护电脑 p 。 
2. "S p q" (1 <= p, q <= N),表示测试电脑 p 和 q 是否能够通信。  
问所有的测试操作中,可以通信的测试个数。

分析:

注意时间限制是10秒。。。。
既然如此,就简单了。
每维护一个电脑,就让它和所有已经维护过的电脑进行比较,
如果距离够,就用并查集合并。
对于每一次的测试操作,查找p  q 的根节点,如果相同,说明可以进行通信,

代码:

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 1010;
int d, r[MAXN];
int F[MAXN];
struct Node
{
    double x, y;
    bool f;
}a[MAXN];

void init(int n)
{
    for (int i = 1; i <= n; i++)
        r[i] = i, a[i].f = false;
}

int Find(int x)
{
    return x == r[x] ? x : r[x] = Find(r[x]);
}

bool Join(int p, int q)
{
    int rp = Find(p);
    int rq = Find(q);
    double D = (a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y);
    D = sqrt(D);
    if (rp != rq && D <= d) {
        r[rp] = rq;
        return true;
    }
    return false;
}

int main()
{
    char c[2];
    int n, p, q, len = 0;
    cin >> n >> d;
    init(n);
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf", &a[i].x, &a[i].y);

    while (scanf("%s %d", &c, &p)!=EOF)
    {
        if (c[0] == 'S')
        { // 测试
            scanf("%d", &q);
            if (!a[p].f || !a[q].f || Find(p)!=Find(q))
                cout << "FAIL" << endl;
            else
                cout << "SUCCESS" << endl;
        }
        else
        {
            a[p].f = true;
            F[len++] = p;
            for (int i = 0; i < len-1; i++)
                Join(F[i],p);
        }
    }
    return 0;
}

Simple And Clear