一个点每过一个单位时间就会向四个方向扩散一个距离，如图。
两个点$a$、$b$连通，记作$e(a,b)$,当且仅当$a$、$b$的扩散区域有公共部分。连通块的定义是块内的任意两个点$u$、$v$都必定存在路径$e(u,a_0),e(a_0,a_1),\cdots,e(a_k,v)$。给定平面上的$n$个点，问最早什么时刻它们形成一个连通块。
一看$n\lt 50$？随便搞即可。
考虑若$n\lt 10^3$怎么做。
考虑每个点$(x_1,y_1)$和$(x_2,y_2)$形成联通块所需要的时间为
$$\frac{|x_1-x_2|+|y_1-y_2|}{2}$$
故我们需要求一个生成树，其中对于每个点$(u,v)$，$\frac{|x_u-x_v|+|y_u-y_v|}{2}$最小。
$\rm Kruskal$算法即可，时间复杂度$O(n^2\log n^2)$。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int MAXN = 55;
6
7 int fa[MAXN], x[MAXN], y[MAXN], n, tot = 0, maxn = 0;
8
9 int find(int x) {
10 return fa[x] == x ? fa[x] : (fa[x] = find(fa[x]));
11 }
12
13 void merge(int x, int y) {
14 fa[find(y)] = find(x);
15 }
16
17 struct edge {
18 int from, to;
19
20 edge() {
21
22 }
23 edge(int jbk, int stt) {
24 from = jbk; to = stt;
25 }
26 } edges[MAXN * MAXN];
27
28 int ha(edge a) {
29 return abs(x[a.from] - x[a.to]) + abs(y[a.from] - y[a.to]);
30 }
31
32 bool cmp(edge a, edge b) {
33 return ha(a) < ha(b);
34 }
35
36 int main() {
37 ios::sync_with_stdio(false);
38 cin >> n;
39 for(int i = 0; i < n; i++)
40 fa[i] = i;
41 for(int i = 0; i < n; i++) {
42 cin >> x[i] >> y[i];
43 }
44 for(int i = 0; i < n; i++)
45 for(int j = 0; j < i; j++) {
46 edge v(i, j);
47 edges[tot++] = v;
48 }
49 sort(edges, edges + tot, cmp);
50 for(int i = 0; i < tot; i++)
51 if(find(edges[i].from) != find(edges[i].to)) {
52 maxn = max(ha(edges[i]), maxn);
53 merge(edges[i].from, edges[i].to);
54 }
55 cout << (int)(ceil(maxn / 2.0)) << endl;
56 return 0;
57 }
转载于:https://www.cnblogs.com/zhylj/p/9523408.html