hdu 5809 Ants kd树+并查集

缘起

继续学习kd树~ hdu 5809 Ants

分析

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
二维平面有N(<=10^5)个蚁穴，每个蚁穴的蚂蚁会不断的爬向最近的蚁穴(距离相同则按x,y坐标选最小的)，
Q(<=10^5)个查询，问两个蚁群是否会相遇。

【输入】
多样例. 每个样例开始于N和Q, 然后是N行. 然后是N行, 每行包含2个整数xi和yi (-1 000 000 000 <= xi, yi <= 1 000 000 000), 然后是Q行,每行两个正整数i和j (1 <= i, j <= N, i ≠ j), 

【输出】
YES表示会相遇, NO表示不会相遇

【样例输入】
2
2 1
0 0
-1 1
1 2
5 2
1 1
3 3
4 4
0 -3
0 -4
1 3
2 4

【样例输出】
Case #1:
YES
Case #2:
YES
NO

【限制】
3s

首先要正确理解题意——蚂蚁从一个蚁群爬到另一个蚁群, 然后又会爬到再另外一个蚁群. 其实行走过程就像不断寻找、逼近最近点对，最终在最近点对中循环，那么落入同一个最近点对的蚂蚁就会相遇。即把每个点和离他最近的点连边，不必考虑方向，同一个连通分量中的蚂蚁一定会相遇。建立图之后用并查集维护一下连通关系即可。

所以算法很简单了

  1. 用kd树预处理所有蚁群成为无向图. A的最近蚁群是B, 则A和B之间连边.
  2. 用并查集维护该无向图的连通分量即可. 然后对每个询问, 通过并查集找爹就知道他们最后会不会堕入同一个最近点对从而一定相遇.
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#include <math.h>
//#define LOCAL
const int maxn = 100005, k = 2;
int n,q, depth, f[maxn], ans,change[maxn]; // change[i]是原先最初输入的input[i]变动到的kdTree中的索引
typedef long long LL;
LL ans_dis;
const LL inf = ~0ULL>>1;
#define SQUARE(x) ((x)*(x))

struct KdTreeNode
{
	LL x[2];
	int index;
	bool flag;
	bool operator<(const KdTreeNode &o) const
	{
		return x[depth%k] < o.x[depth%k];
	}
}kdTree[maxn<<2], input[maxn];

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

void merge(int i,int j)
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	if (f[fi]<f[fj])
	{
		f[fi]+=f[fj];
		f[fj] = fi;
	}
	else
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
}

void build(int begin, int end, int cur, int dep)
{
	if (begin>end)
	{
		return;
	}
	depth = dep%k;
	int mid = (begin+end)>>1;
	nth_element(input+begin, input+mid, input+end+1);
	kdTree[cur] = input[mid];
	kdTree[cur].flag = true;
	change[input[mid].index] = cur; // 原先的input[mid].index变动到了cur
	build(begin, mid-1, cur<<1, dep+1);
	build(mid+1, end, cur<<1|1, dep+1);
}

void query(KdTreeNode &target, int cur, int dep)
{
	KdTreeNode curNode = kdTree[cur];
	if (!curNode.flag)
	{
		return;
	}
	if (curNode.index !=  target.index) // 检验当前节点, 不能和自己最近
	{
		LL dis = SQUARE(target.x[0]-curNode.x[0]) + SQUARE(target.x[1] - curNode.x[1]);
		if (!ans || dis<ans_dis)
		{
			ans = curNode.index;
			ans_dis = dis;
		}
		else if (dis==ans_dis && (curNode.x[0]<kdTree[change[ans]].x[0] ||(curNode.x[0]==kdTree[change[ans]].x[0] && curNode.x[1]<kdTree[change[ans]].x[1]))) // 如果距离相等, 则选择坐标小的那个
		{
			ans = curNode.index;
			ans_dis = dis;
		}
	}
	int idm = dep%k;
	int tx = target.x[idm]<curNode.x[idm]?(cur<<1):(cur<<1|1);
	int ty = tx^1;
	query(target, tx, dep+1);
	if (SQUARE(target.x[idm]-curNode.x[idm])<=ans_dis) // 因为要求某种极小, 所以要考虑<=的情况
	{
		query(target, ty, dep+1);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int i = 1; i<=kase; i++)
	{
		printf("Case #%d:\n", i);
		memset(f, -1, sizeof(f));
		memset(kdTree, 0, sizeof(kdTree));
		scanf("%d%d",&n,&q);
		for (int i = 1; i<=n; i++)
		{
			scanf("%lld%lld", &input[i].x[0], &input[i].x[1]);
			input[i].index = i;
		}
		build(1,n,1,0);
		for (int i = 1; i<=n;i++)
		{
			ans = 0, ans_dis = inf;
			query(input[i], 1, 0);
			merge(input[i].index, ans); // 维护并查集
		}
		while(q--)
		{
			int x,y;
			scanf("%d%d", &x, &y);
			getf(x)==getf(y)?puts("YES"):puts("NO");
		}
	}
	return 0;
}

注意, 本题比较坑的地方在于inf, 因为坐标差距的范围到了 20亿, 所以欧式距离的平方可达 8*10^18.

而long long 的范围是 9*10^18. 所以inf要取好, 不能取 1LL<<62, 这是不够的（只有4*10^18）. 要用 ~0ULL>>1

ac情况

Status Accepted
Time 1825ms
Memory 13752kB
Length 2594
Lang G++
Submitted 2019-09-23 11:36:31
Shared
RemoteRunId 30684035

最后谈一下kd树的方差优化. 其实就是你在build kd树的时候, 选择二分的轴线并不是用depth = dep%k;, dep+1 这样获取用于nth_element的depth. 而是每次计算各个轴向的方差, 每次都选择方差最大的那个轴向作为二分的轴向（即更改第56行代码depth的获取）. 虽然这将引入额外的复杂度. 但是你构建kd树只有一次. 均摊下来还是比较划算的. 可以用来过一些比较刁钻的数据（这些数据专门用来卡depth%k的建树方法）. 但是正如你看到的, 使用depth = dep%k;, dep+1 依旧可以水过此题而不需要方差优化kd树. 而且实际工程开发（例如大规模数据挖掘），数据的趋势不明显的时候, depth = dep%k;, dep+1 这样建立的kd树的效果还是相当可以的. 算法竞赛一般也不会卡这种建树方法.