Wireless Network

一时失言乱红尘 2022-01-08 00:11 165阅读 0赞

题目链接:http://poj.org/problem?id=2236

注意:题目中说的是 1~n,所以,在初始化根节点的时候不要弄成 0 ~ n-1这种(for(int i = 0;i < n;i++) 这种是不对的,如果这样,则造成n没有对应的根节点,因为初始化的时候根本没有初始化到n

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<cstring>
     5 using namespace std;
     6 
     7 const int maxn = 1010;
     8 
     9 struct node {
    10     int x,y;
    11     bool open;
    12 }arr[maxn];
    13 int f[maxn];
    14 int n,d;
    15 
    16 void Init(int n) {
    17     for(int i = 1;i <= n;i++)
    18         f[i] = i;
    19 }
    20 
    21 int FindRoot(int x) {
    22     if(x == f[x])
    23         return x;
    24     f[x] = FindRoot(f[x]);
    25     return f[x];
    26 }
    27 
    28 double Count(node a,node b) {
    29     return sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2));
    30 }
    31 
    32 void Union(int x) {
    33     int a = FindRoot(x);
    34     for(int i = 1;i <= n;i++) {
    35         int b = FindRoot(i);
    36         if(arr[i].open && Count(arr[i],arr[x]) <= d)
    37             f[b] = a;
    38     }
    39 }
    40 
    41 int main() {
    42     while(scanf("%d%d",&n,&d) != EOF) {
    43         Init(n);
    44         for(int i = 1;i <= n;i++) {
    45             scanf("%d%d",&arr[i].x,&arr[i].y);
    46             arr[i].open = false;
    47         }
    48         char ch;
    49         int x,y;
    50         while(cin>>ch) {
    51             if(ch == 'O') {
    52                 scanf("%d",&x);
    53                 arr[x].open = true;
    54                 Union(x);
    55             }
    56             else {
    57                 scanf("%d%d",&x,&y);
    58                 if(FindRoot(x) == FindRoot(y))
    59                     printf("SUCCESS\n");
    60                 else
    61                     printf("FAIL\n");
    62             }
    63         }
    64     }
    65     return 0;
    66 }

转载于:https://www.cnblogs.com/youpeng/p/10372419.html