POJ - 2236 Wireless Network （kuangbin - 并查集）

题目描述(已转换成中文)

  南亚发生了一次地震。ACM (Asia Cooperated Medical 亚洲联合医疗队) 已经为膝上型电脑搭建了一个无线网络，但受到了一次不可预知的余震攻击，因此网络中的所有电脑都被破坏了。电脑被逐台修复，网络逐步恢复了工作。由于受到硬件的约束，每台电脑只能与距离它不超过 d 米的其它电脑直接通信。但每台电脑可被看作其它两台电脑的通信中转点，也就是说，如果电脑 A 和电脑 B 可以直接通信，或存在一台电脑 C 既可与 A 也可与 B 通信，那么电脑 A 和电脑 B 之间就能够通信。

  在处理网络修复的过程中，工作人员们在任何一个时刻，可以执行两种操作：维修一台电脑，或测试两台电脑是否能够通信。请您找出全部的测试操作。

输入格式

  第一行包含了两个整数 N 和 d (1 <= N <= 1001, 0 <= d <= 20000)。此处 N 是电脑的数目，编号从 1 到 N；同时，D 是两台电脑之间能够直接通信的最大距离。接下来的 N 行，每行包含两个整数 xi, yi (0 <= xi, yi <= 10000)，表示 N 台电脑的坐标。从第 (N+1) 行到输入结束，是逐一执行的操作，每行包含一个操作，格式是以下两者之一：   1. “O p” (1 <= p <= N)，表示维护电脑 p 。   2. “S p q” (1 <= p, q <= N)，表示测试电脑 p 和 q 是否能够通信。   输入不超过 300000 行。

输出格式

  对于每个测试操作，如果两台电脑能够通信，则打印 “SUCCESS”；否则，打印 “FAIL”。

输入输出样例

输入

4 1 0 1 0 2 0 3 0 4 O 1 O 2 O 4 S 1 4 O 3 S 1 4

输出

FAIL SUCCESS

题目链接

分析：

  这道题是属于并查集类型的题目，标志：每台电脑可被看作其它两台电脑的通信中转点，也就是说，如果电脑 A 和电脑 B 可以直接通信，或存在一台电脑 C 既可与 A 也可与 B 通信，那么电脑 A 和电脑 B 之间就能够通信。换句话说，两个电脑若已被维修，且两个电脑之间的距离符合能够通信的条件，两个电脑即处于同个集合，每个集合里的电脑都可以直接或者间接与同个集合中的其他电脑进行通信。首先，定义一个结构体，用于储存每台电脑的坐标，接着定义一个a数组，是标记后续操作中被维修了的电脑(a[i] = 1表示i电脑已被维修)，定义一个vis二维数组，用于记录两点之间的距离是否符合通信要求(若vis[i][j] == 1，则表示第i台电脑和第j台电脑之间的距离符合通信条件)，如果两台电脑都已被维修(a[i] == 1 && a[j] == 1) 且vis[i][j] == 1，则可以把两台电脑归为一个集合。在主函数外定义一个pre函数，判断之前输入的所有电脑坐标中，每台电脑之间的距离是否符合通信条件，通过vis数组进行标记。另外，还要定义一个fu数组，这是记录第i台电脑的父节点fu[i]，方便于后续对元素集合的合并，且便于对元素所在集合根节点的查找，在遍历读入i台电脑坐标的同时，把fu数组初始化(fu[i] = i)。在主函数外定义found函数和unit函数(并查集类型的题目常规模板)，found函数用于查找集合中某个元素的根节点，unit函数用于合并两个集合(找到其中某个元素所在集合的根节点，并把根节点的父节点由本身指向另一个集合根节点的父节点，这样就实现了两个集合的合并)，主函数中输入后续操作，若是维修电脑，则与符合条件的其他电脑进行合并；若是判断两个电脑之间是否可以进行通信，则可以把问题转换为判断两个电脑是否处于同一个集合里面，即判断两个元素的根节点是否相同即可。

这道题需要注意的地方：

  pre函数是利用vis数组标记两点之间的距离是否满足通信要求，在第二个for循环里边j我们只需从i + 1开始，这样也能遍历到元素之间两两的距离，但要注意在对vis数组进行标记的时候，vis[i][j]和vis[j][i]分别表示从i到j的距离和从j到i的距离，两者实质是相同的，因为之前j是从i + 1开始，所以i和j符合通信距离的标记应为vis[i][j] = vis[j][i] = 1。如果第二个for循环里面j从0开始，就产生了不必要的判断步骤，因为i到j的距离 和 j到i的距离是一样的。

代码如下：

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; const int maxn = 1005; int n, d, vis[maxn][maxn], a[maxn], fu[maxn]; int read(){ int x, f = 1; char ch; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1; x = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48; return x * f; } struct node{ //记录每台电脑的坐标 int x, y; }u[maxn]; void pre(){ //标记所有电脑间，两两的通信距离是否符合条件 int i, j, dx, dy; for(i = 1; i <= n; i++){ for(j = i + 1; j <= n; j++){ dx = u[i].x - u[j].x; dy = u[i].y - u[j].y; if(dx * dx + dy * dy <= d * d) vis[i][j] = vis[j][i] = 1; else vis[i][j] = vis[j][i] = 0; } } } int found(int x){ //寻找某个元素的根节点 if(fu[x] == x) return x; return fu[x] = found(fu[x]); } void unit(int x, int y){ //对两个元素所在的集合进行合并 if(found(x) == found(y)) return; else fu[found(x)] = found(y); } int main(){ int i ,j, t, x, y; char c; n = read(); d = read(); for(i = 1; i <= n; i++){ u[i].x = read(); u[i].y = read(); fu[i] = i; } pre(); while(~scanf("%c", &c)){ if(c == 'O'){ t = read(); a[t] = 1; for(i = 1; i <= n; i++){ if(a[i] && vis[i][t]){ unit(t, i); } } } else{ x = read(); y = read(); if(found(x) == found(y)) printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }