基本概念

和常规意义下最小生成树的概念类似,该算法用于求解在二维平面上所有点的最小生成树.两点之间的距离定义为曼哈顿距离.

原理

如果使用朴素的求法,时间复杂度为

O(n^2logn)

而点的数据规模一般在1e5左右,这个复杂度是无法接受的.所以,需要根据曼哈顿距离的特殊性质,删去大量的无用边,进而优化算法.

首先以任意一点为坐标原点,做出y=x和y=-x两条直线,将坐标轴分成八个部分.如下图所示:

考虑R1这一部分.如果在这一区间内存在一点P和A点的距离最小,则连接一条从A到该点的边.假如这部分里存在另外一点Q,该点到A的距离没有P到A的距离小,则不进行连边.因为有

|AP|>|AQ|->|AQ|>|PQ|

(证明略).所以在生成树上一定是P和A连边,而不是Q和A连边.

由于对称性,划分出的八个区域只需要计算上图中的四个区域即可.接下来考虑如何找出距离原点最近的点.经过推导,四个区域依次有如下条件:

x_i \leq x \ \ y_i-x_i \leq y-x

y_i \leq y \ \ y-x \leq y_i-x_i

y \leq y_i \ \ y_i+x_i \leq y+x

x_i \leq x \ \ y+x \leq y_i+x_i

(原点坐标为(x_i,y_i)),其他点坐标为(x,y)

其中第一个条件可以排序解决,第二个条件则可以使用树状数组解决.

关于分别计算这四种情况有个技巧,可以通过对称变换将其转化为求R1区域的情况.如下图所示:

关于y=x对称后:

关于y轴对称后:

再关于y=x对称后:

模板

inline void Change(int l,int r,int p){
    int i=0;
    for (i=l;i;i-=bit(i))
        if (t[i].x>r)   t[i].x=r,t[i].id=p;
}

inline void Add(int s,int t,int fl){
    e[lsum].x=s;    e[lsum].y=t;    e[lsum++].id=fl;
}

for (dir=1;dir<=4;dir++){
    if ((dir%2)==0)
        for (i=1;i<=n;i++)  Swap(a[i].x,a[i].y);
    if (dir==3)
        for (i=1;i<=n;i++)  a[i].x*=-1;
    sort(a+1,a+1+n,cmp);
    for (i=1;i<=n;i++)  b[i]=a[i].y-a[i].x,l[i]=&b[i];
    sort(l+1,l+1+n,Cmp);
    for (i=1;i<=n;i++)  *l[i]=i;
    for (i=1;i<=n;i++)  t[i].x=INF,t[i].id=-1;
    for (i=n;i;i--){
        pos=Query(b[i]);
        if (pos!=-1)
            Add(a[i].id,a[pos].id,Dis(i,pos));
        Change(b[i],a[i].x+a[i].y,i);
    }
}

例题

[POJ23241]Object Clustering

题意:

求曼哈顿距离最小生成树上第K大的边.

代码:

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 10010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define bit(x) (x&(-x))
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,lsum=1,dir,pos,x,y,ss;
int b[N],f[N],*l[N];

struct Data{
    int x,y,id;
}a[N],t[N],e[N*8];

inline bool cmp2(Data x,Data y){return x.id<y.id;}
inline bool Cmp(const int *a,const int *b){return *a<*b;}
inline bool cmp(Data x,Data y){return (x.x==y.x)?x.y<y.y:x.x<y.x;}

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline int Dis(int x,int y){
    return Abs(a[x].x-a[y].x)+Abs(a[x].y-a[y].y);
}

inline int Query(int x){
    int i=0,Ans=INF,id=-1;
    for (i=x;i<=n;i+=bit(i))
        if (t[i].x<Ans) Ans=t[i].x,id=t[i].id;
    return id;
}

inline void Change(int l,int r,int p){
    int i=0;
    for (i=l;i;i-=bit(i))
        if (t[i].x>r)   t[i].x=r,t[i].id=p;
}

inline void Add(int s,int t,int fl){
    e[lsum].x=s;    e[lsum].y=t;    e[lsum++].id=fl;
}

inline int Find(int x){return (x==f[x])?x:f[x]=Find(f[x]);}

int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].id=i;
    }
    for (dir=1;dir<=4;dir++){
        if ((dir%2)==0)
            for (i=1;i<=n;i++)  Swap(a[i].x,a[i].y);
        if (dir==3)
            for (i=1;i<=n;i++)  a[i].x*=-1;
        sort(a+1,a+1+n,cmp);
        for (i=1;i<=n;i++)  b[i]=a[i].y-a[i].x,l[i]=&b[i];
        sort(l+1,l+1+n,Cmp);
        for (i=1;i<=n;i++)  *l[i]=i;
        for (i=1;i<=n;i++)  t[i].x=INF,t[i].id=-1;
        for (i=n;i;i--){
            pos=Query(b[i]);
            if (pos!=-1)
                Add(a[i].id,a[pos].id,Dis(i,pos));
            Change(b[i],a[i].x+a[i].y,i);
        }
    }
    sort(e+1,e+lsum,cmp2);
    for (i=1;i<=n;i++)  f[i]=i;
    ss=n;
    for (i=1;i<lsum;i++){
        x=Find(e[i].x); y=Find(e[i].y);
        if (x==y)   continue;
        f[x]=y; ss--;
        if (ss==m)  {
            printf("%d\n",e[i].id); break;
        }
    }
    return 0;
}