POJ-2236 Wireless Network

teach

简单并查集题解

Wireless Network

原题链接：https://vjudge.net/contest/165746#problem/A

问题描述

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.

题意

有n台电脑，给出这n台电脑的坐标，所有电脑的初始状态全部是断电的，电脑与电脑之间如果要直接相连，必须是距离相差在最大范围d以内。现在进行一系列操作，按要求输出。
操作一共有2种：
1.开启一台电脑的电源。
2.查询两台电脑是否能相互联系（直接、间接），若能，则输出SUCCESS，若不能，则输出FAIL。

Input

The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 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 <= xi, yi <= 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. “O p” (1 <= p <= N), which means repairing computer p.
  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

题解

题意很简单，就是一个普通的并查集，我们要做的就是每次激活了一台电脑就从1-n扫一次，找到激活了，而且在它距离里的电脑，跟它做一次并查集。当然，这里的并查集做了优化，就是同时指向了它的最高级祖先，这样做的效果就是8秒的程序2秒跑完了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<stack>
#include<bitset>
#include<cstdlib>
using namespace std;
1
2
3
4
5
6
#define mem(a) memset(a,0,sizeof(a))
#define rep(i,a,n) for(int i=a; i<n; i++)
#define rep1(i,a,n) for(int i=n-1; i>=a; i--)
#define s(a) scanf("%d",&a)
#define test(a) cout<<a<<endl
#define test2(a,b) cout<<a<<" "<<b<<endl
1
2
3
4
5
6
typedef long long ll;
const int MAX = 1016;
const int MAX = 1016;
const int N = 1e3+10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int a[N][2],v[N],f[N];
int d;
int calculate(int x1,int x2,int y1,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int find_father(int x)
{
    int root=x,temp;
    while(f[root]!=root) root=f[root];
    while(f[x]!=x)
    {
        temp=x;
        x=f[x];
        f[temp]=root;
    }
    return x;
}
void combine_father(int i,int x)
{
    if(calculate(a[i][0],a[x][0],a[i][1],a[x][1])>d*d) return;
    x=find_father(x);
    i=find_father(i);
    if(i!=x) f[x]=i;
}
int main()
{
    mem(v);
    mem(a);
    int n;
    char choice;
    scanf("%d%d",&n,&d);
    rep(i,0,n)
     {
         scanf("%d%d",&a[i][0],&a[i][1]);
         f[i]=i;
     }
    getchar();
    while(scanf("%c",&choice)!=EOF)
    {
        if(choice=='S')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--; y--;
            getchar();
            if(find_father(x)==find_father(y))
                cout << "SUCCESS" << endl;
            else
                cout << "FAIL" << endl;
        }
        else
        {
            int x;
            s(x);
            x--;
            getchar();
            v[x]=true;
            rep(i,0,n)
            if(i!=x&&v[i])
             combine_father(i,x);
        }
    }
    return 0;
}

写在最后

#define IOS ios::sync_with_stdio(false);cin.tie(0)

这句就是让我在这题里wa了5次的罪归祸首!!! 其实这句话是为了能让cin的扫入方式改变，然后它的速度就能媲美scanf，然而，因为它的存在，scanf和printf就不能使用了，否则会出现bug！！
所以一句话，早用scanf，早accepted.