poj 2236 Wireless Network 并查集

缘起

日常浪费生命 poj 2236 Wireless Network

分析

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
有一个计算机网络的所有线路都坏了，网络中有n台计算机，现在你可以做两种操作，修理（O）和检测两台计算机是否
连通（S），只有修理好的计算机才能连通。连通有个规则，两台计算机的距离不能超过给定的最大距离D（一开始会给
你n台计算机的坐标）。检测的时候输出两台计算机是否能连通。

【输入】
第一行给出n和d（1 <= N <= 1001, 0 <= d <= 20000），计算机被标记为1~n
然后n行每行两个数字xi和yi(0 <= xi, yi <= 10000),
然后是多行，每行分别代表一种操作——修改或者测试
O p， 1 <= p <= N，表示修复电脑p
S p q, 1 <= p, q <= N，表示测试p和q是否连通

【输出】
对于测试操作，打印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

【限制】
10s

【来源】
poj月赛

思路比较裸，就是并查集。 首先读入坐标之后，O（n^2）维护一张邻接矩阵（或者邻接表）. g[i][j]为true的话，表示距离<=d, 否则就是距离>d.

然后对于修复电脑p的操作，遍历与p距离<d的电脑, 如果此电脑没修好的话，则罢了, 如果修好了，则做并查集merge操作. 对于测试连通的操作，就是并查集找爹的操作.

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
//#define LOCAL
typedef vector<int>::iterator vit;

int n,d, x[1005], y[1005],f[1005]; // f是并查集数组

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]);
}

void merge(int x, int y)
{
	int fx = getf(x), fy = getf(y);
	if (fx==fy)
	{
		return; // 已经在一起了, 即连通
	}
	if (f[fx]<f[fy]) // 如果x所在树是更多元素的,则需要将y所在树并入x所在树
	{
		f[fx]+=f[fy];
		f[fy] = fx;
	}
	else
	{
		f[fy]+=f[fx];
		f[fx]=fy;
	}
}

int dis(int x,int y, int a, int b)
{
	return (x-a)*(x-a)+(y-b)*(y-b);
}

vector<int> g[1005];
bool alive[1005]; // 是否修复

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(f,-1,sizeof(f));
	scanf("%d%d", &n, &d);
	d = d*d;
	for (int i = 1; i<=n;i++)
	{
		scanf("%d%d", x+i,y+i);
	}
	for (int i = 1; i<=n; i++)
	{
		for (int j = i; j<=n; j++)
		{
			if (dis(x[i], y[i], x[j],y[j])<=d) // 电脑i和电脑j距离<=d
			{
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}
	getchar();
	char cmd;
	int p,q;
	while(~(cmd = getchar()))
	{
		if (cmd=='O') // 修复电脑p
		{
			scanf("%d", &p);
			alive[p] = true;
			for (vit i = g[p].begin(); i!=g[p].end(); i++)
			{
				if (alive[*i]) // 如果尚未修复,则算了
				{
					merge(p, *i);
				}
			}
		}
		else // 测试p和q的连通性
		{
			scanf("%d%d", &p, &q);
			getf(p)==getf(q)?puts("SUCCESS"):puts("FAIL");
		}
		getchar(); // 吸收多余换行符
	}
	return 0;
}

ac情况

Status Accepted
Time 969ms
Memory 4476kB
Length 1420
Lang C++
Submitted 2019-08-30 10:02:05
Shared
RemoteRunId 20818018