曼哈顿距离
我们通常所指的距离是欧拉距离，这种距离体系很好的满足了三角形不等式，也合理地体现了空间中距离的大小关系。但是这一类距离在某些场合，甚至实际生活中却不太适用。
如图为美国纽约曼哈顿，在这里，距离的定义大概是 $dis(A,B)=\abs{A_x-B_x}+\abs(A_y-B_y)$，因为你只能沿着横平竖直的马路行进。曼哈顿距离的名称也从此而来。
衡量一个距离的定义是否合理，我们一般要检测它是否满足三角形不等式，如：
对于欧拉距离：$$dis(A,B)=\sqrt{(A_x-B_x)^2+(A_y-B_y)^2}<=dis(A,C)+dis(B,C)$$
对于曼哈顿距离：$$dis(A,B)=|A_x-B_x|+|A_y-B_y|<=dis(A,C)+dis(B,C)$$
现在我们已经确定了这种距离的定义是合理的，但是还要注意，
在考虑曼哈顿距离的同时，我们需要注意一下几点：
1. 欧拉距离在进行了坐标系的线性变换之后依然不变，但是曼哈顿距离却会随坐标轴的方向变化。几种情况例外，就是当反转 x 轴或 y 轴，以及交换 x,y 轴时。
2. 到某个点曼哈顿距离相同的点的集合是一个斜的正方形。这个结论在思考和分析过程中非常有用。
曼哈顿距离生成树
对于平面上的两个点，如果用最短的平行于坐标轴的折线连接，折线的长度就是这两个点的曼哈顿距离。
对于平面上的多个点，选取适当的点以上述折线连接，使得所有点联通，构成这些点的曼哈顿距离生成树。
折线总长度最小的曼哈顿距离生成树叫做曼哈顿距离最小生成树。
如何求出曼哈顿距离生成树呢？
最简单的想法是：先将平面上的 n 个点暴力连边，再用 kruskal 算法求解。时间复杂度约 $O(n^2log(n))$
注意到这种算法将许多没有意义的边连接了，所以我们需要分析如何才能高效地连接有意义的边。
引理 1：对于一个点，我们只需要连接每个 1/8 象限内的离它最近的点。
需要证明若 A 为离 O 最近的点，连边 (O,A),(A,B) 比 (O,A),(O,B) 优，同时对于 C 也类似。
已知：$A_x+A_y<B_x+B_y$
需要证明：$(O,A)+(A,B)<(O,A)+(O,B)$
证：
因为：
$$
(O,A)+(A,B)=A_x+A_y+|B_x-A_x|+|B_y-A_y|
$$
$$
(O,A)+(O,B)=A_x+A_y+B_x+B_y
$$
所以只需证
$$
|B_x-A_x|+|B_y-A_y|<B_x+B_y
$$
拆开绝对值符号分别得到：
$$
-A_x-A_y<0
$$
$$
A_y-A_x<2B_y
$$
$$
A_x-A_y<2B_x
$$
$$
A_x+A_y<2B_x+2B_y
$$
分别都可以证明是对的。其他象限也可以如此证明。
因此我们已经证明了引理 1，就可以用它来建立生成树了。
寻找最近点
如何寻找最近的点成为了一个问题。如果我们遍历所有的点，与之前的暴力连边没有什么改进。因此我们会借助一定的遍历次序，和优秀的数据结构。
对于如图的 1/8 象限内的所有点 A, 离 O 最近的点一定是 $A_x+A_y$最小的那一个。为了找到那一个点，我们需要限制一下几个条件：
$$
A_y-A_x>=0
$$
$$
X>=0
$$
对于第一个条件，我们可以用线段树的区间表示，线段树的每一个区间 [a,b] 表示当前 A_y-A_x∈[a,b] 的所有点中 A_x+A_y 最小的一个。
对于第二个条件，我们可以按照 X 降序遍历。
至此，我们解决了所有问题，曼哈顿距离最小生成树问题也初步得到了解决。
扩展：
1. 如果点的范围比较大，需要进行离散化。
2. 对于动态更新的类似问题，请参考 http://www.doc88.com/p-998527952232.html
题目
一道裸题：51NOD1213 求曼哈顿距离最小生成树的边长度之和。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MX 50005
#define MT 2000010
#define ME 1000005
#define MOV 1000001
#define oo 90000000
#define ls (node<<1)
#define rs (node<<1|1)
#define mid ((l+r)>>1)
#define dis(a,b) (abs((a).x-(b).x)+abs((a).y-(b).y))
using namespace std;
typedef struct point
{
int x,y,id;
}points;
typedef struct tnode
{
int mn,id;
}segtre;
points pot[MX];
segtre tre[MT<<2];
int fst[MX],nxt[ME],u[ME],v[ME],w[ME],lnum;
int fa[MX];
int ord[ME];
int n;
inline void addeg(int nu,int nv,int nw)
{
nxt[++lnum]=fst[nu];
fst[nu]=lnum;
u[lnum]=nu;
v[lnum]=nv;
w[lnum]=nw;
}
int findfa(int x)
{
return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
inline void upd(int node)
{
if(tre[ls].mn<tre[rs].mn)tre[node].mn=tre[ls].mn,tre[node].id=tre[ls].id;
else tre[node].mn=tre[rs].mn,tre[node].id=tre[rs].id;
}
void build(int node,int l,int r)
{
tre[node].mn=+oo;
tre[node].id=-1;
if(l!=r)build(ls,l,mid),build(rs,mid+1,r);
}
void cng(int l,int r,int node,int p,int x,int id)
{
if(l==r)tre[node].mn=x,tre[node].id=id;
else if(p<=mid)cng(l,mid,ls,p,x,id),upd(node);
else cng(mid+1,r,rs,p,x,id),upd(node);
}
segtre qmn(int l,int r,int node,int ql,int qr)
{
segtre nul,a,b;
nul.mn=+oo;
nul.id=-1;
if(ql<=l&&r<=qr)return tre[node];
else if(ql>r||qr<l)return nul;
else
{
a=qmn(l,mid,ls,ql,qr);
b=qmn(mid+1,r,rs,ql,qr);
if(a.mn<b.mn)return a;
else return b;
}
}
inline bool cmpx(points a,points b)
{
return (a.x!=b.x)?(a.x>b.x):a.y>b.y;
}
inline bool cmpe(int a,int b)
{
return w[a]<w[b];
}
inline void sector1()
{
segtre near;
for(int i=1;i<=n;i++)
{
near=qmn(1,MOV<<1,1,MOV+pot[i].y-pot[i].x,+oo);
if(near.mn==+oo||near.id==-1);
else
{
addeg(pot[i].id,near.id,near.mn-pot[i].x-pot[i].y);
addeg(near.id,pot[i].id,near.mn-pot[i].x-pot[i].y);
}
cng(1,MOV<<1,1,MOV+pot[i].y-pot[i].x,pot[i].x+pot[i].y,pot[i].id);
}
}
long long cruskal()
{
long long ans=0,cnt=0;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=lnum;i++)ord[i]=i;
sort(ord+1,ord+lnum+1,cmpe);
for(int i=1;i<=lnum;i++)
{
if(findfa(u[ord[i]])!=findfa(v[ord[i]]))
{
ans+=(long long)w[ord[i]];
cnt++;
fa[findfa(u[ord[i]])]=findfa(v[ord[i]]);
}
if(cnt>=n-1)break;
}
return ans;
}
void work()
{
sort(pot+1,pot+n+1,cmpx);
build(1,1,MOV<<1);
sector1();
for(int i=1;i<=n;i++)pot[i].x=-pot[i].x+MOV;
sort(pot+1,pot+n+1,cmpx);
build(1,1,MOV<<1);
sector1();
for(int i=1;i<=n;i++)swap(pot[i].x,pot[i].y);
sort(pot+1,pot+n+1,cmpx);
build(1,1,MOV<<1);
sector1();
for(int i=1;i<=n;i++)pot[i].y-=MOV,pot[i].y*=-1;
sort(pot+1,pot+n+1,cmpx);
build(1,1,MOV<<1);
sector1();
printf("%lld\n",cruskal());
}
void input()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&pot[i].x,&pot[i].y),pot[i].id=i;
}
int main()
{
input();
work();
return 0;
}
0 条评论