概念

给定二维平面上的N个点,在两点之间连边的代价为其曼哈顿距离($d_{ij} = |x_i - x_j| + |y_i - y_j|$),求使所有点连通的最小代价。

处理出所有的边$O(n^2)$,然后用Prim或Kruskal,复杂度为 $O(n^3)$ 或 $O(n^2logn)$

然而曼哈顿距离有特殊性质,在最小生成树中可以得出这样一个结论:
以一个点为原点建立直角坐标系,在每45度内只会向距离该点最近的一个点连边

证明

然后我们可以在四个方向(由于边有对称性不用八个方向)上处理出每个点到另一个点的最短距离
处理四次,每次进行坐标变换就行了
将点先x后y排序,然后维护一个树状数组,下标为y-x(因为在某个点$(x_0,y_0)$y轴顺时针方向45°的范围内的点$y - x > y_0 - x_0$,需要离散化),记录的是$x+y$最小的点,也就是距离最小的点。
这样最多有4n产生边,现在在这个图做Kruskal就行了,复杂度为$O(nlogn)$

模板

LA3662

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<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int n,pn,cnt,b[maxn],fa[maxn];

struct Point{
int x,y;
int id;
bool operator<(const Point& rhs) const
{
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
} p[maxn];

struct Edge{
int u,v;
LL d;
bool operator<(const Edge& rhs) const
{
return d < rhs.d;
}
} e[maxn<<2];

void addEdge(int u,int v,LL d)
{
e[cnt].u = u;
e[cnt].v = v;
e[cnt++].d = d;
}

struct Bit{
int mn,pos;
void init()
{
mn = INF;
pos = -1;
}
} bit[maxn];

inline int lowbit(int x)
{
return x&-x;
}

void update(int x,int mn,int pos)
{
for(int i=x;i>0;i-=lowbit(i))
{
if(bit[i].mn > mn)
{
bit[i].mn = mn;
bit[i].pos = pos;
}
}
}

int query(int x)
{
int mn = INF,pos = -1;
for(int i = x;i<=pn;i+=lowbit(i))
{
if(bit[i].mn < mn)
{
mn = bit[i].mn;
pos = bit[i].pos;
}
}
return pos;
}

int find(int x)
{
return fa[x] == x?x:fa[x] = find(fa[x]);
}

LL solve()
{
cnt = 0;
for(int dir = 0;dir<4;++dir)
{
if(dir&1) for(int i=0;i<n;++i) swap(p[i].x,p[i].y);
if(dir == 2) for(int i=0;i<n;++i) p[i].x = -p[i].x;
sort(p,p+n);
for(int i=0;i<n;++i) b[i] = p[i].y - p[i].x;
sort(b,b+n);
pn = unique(b,b+n) - b;
for(int i=1;i<=pn;++i) bit[i].init();
for(int i=n-1;i>=0;--i)
{
int pos = lower_bound(b,b+pn,p[i].y - p[i].x) - b + 1;
int po = query(pos);
if(po != -1)
addEdge(p[i].id,p[po].id,abs(p[i].x-p[po].x) + abs(p[po].y-p[i].y));
update(pos,p[i].y + p[i].x,i);
}
}
LL res = 0;
for(int i=0;i<n;++i) fa[i] = i;
sort(e,e+cnt);
for(int i=0;i<cnt;++i)
{
int u = find(e[i].u),v = find(e[i].v);
if(u != v)
{
fa[u] = v;
res += e[i].d;
}
}
return res;
}

int main()
{
//freopen("test.txt","r",stdin);
int kase = 1;
while(scanf("%d",&n) == 1 && n)
{
for(int i=0;i<n;++i)
{
scanf("%d %d",&p[i].x,&p[i].y);
p[i].id = i;
}
LL ans = solve();
printf("Case %d: Total Weight = %lld\n",kase++,ans);
}
return 0;
}

题目

poj3241

将一个图分成k组,求一个最小的X满足每组中的每一点都存在另一点满足其曼哈顿距离$d \leq x$
简单分析后发现求曼哈顿最小生成树上的第K大边即可。