【总结】平面manhattan距离最小生成树的O(nlogn)算法

求平面上个点的曼哈顿距离最小生成树。
然而枚举所有的边,边数会达到.
套用Kruskal算法,总时间复杂度为,显然无法通过最大的数据。
然而条边真的都是有用的吗?
事实上有用的边数级别为.
定理:以每个点为中心划分成的8个45度区域内,有用的边只有点到这个区域内与点曼哈顿距离最小的点之间的边。
以y轴正半轴向右旋转45度形成的轨迹区域举例说明。
设中心点i为,另有两点在此区域内,且,即
由于点A,B在区域内,那么.
(1)若时:

(2)若时:
显然.
.


(3)若时:
与2同理有
(4)若时:
矛盾。
综上:
考虑环,易知将边换为边中较小的一条边总不会使答案增加。
因此定理得证。

那么如何快速的处理出对于每一个点有用的边呢?
假设仅考虑y轴正半轴向顺时针旋转45度的平面区域。
将所有点的横坐标由大到小排序,依次处理。
考虑点,若在以为原点的上述区域中,那么有,即.
.
也就是说对于点,我们只需得到之前处理过的点满足的使得最小的作为答案。
于是我们利用离散,维护的最小值标号。
那么这个区域内可以在的时间完成。
对于别的区域,我们只需对原来点的坐标进行对称变换运行原来的算法即可。

最后套用Kruskal算法,时间复杂度为.

//BZOJ2177
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

inline int getc() {
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, L, stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint() {
    int c;
    while(!isdigit(c = getc()) && c != '-');
    bool sign = c == '-';
    int tmp = sign ? 0 : c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return sign ? -tmp : tmp;
}

#define _abs(x) ((x)>0?(x):(-(x)))

#define N 50010
int n;
int x[N], y[N];
struct Node {
    int x, y, lab;
    Node(int _x = 0, int _y = 0, int _lab = 0):x(_x),y(_y),lab(_lab){}
    bool operator < (const Node &B) const {
        return (x > B.x || (x == B.x && y > B.y)); 
    }
}S[N];

struct Edge {
    int from, to, len;
    Edge(int _from = 0, int _to = 0, int _len = 0):from(_from),to(_to),len(_len){}
    bool operator < (const Edge &B) const {
        return len < B.len;
    }
}E[N << 2];
int top;

int sa[N], rank[N], change[N];
inline bool cmp(const int &a, const int &b) {
    return S[a].y - S[a].x > S[b].y - S[b].x;
}

int A[N];
int ask(int p) {
    int res = 0;
    for(; p; p -= p & -p)
        if (S[change[res]].x + S[change[res]].y > S[change[A[p]]].x + S[change[A[p]]].y)
            res = A[p];
    return res;
}
void modify(int p, int ins) {
    for(; p <= n; p += p & -p)
        if (S[change[ins]].x + S[change[ins]].y < S[change[A[p]]].x + S[change[A[p]]].y)
            A[p] = ins;
}

void AddEdge() {
    register int i, j, k;
    
    for(i = 1; i <= n; ++i)
        sa[i] = i;
    sort(sa + 1, sa + n + 1, cmp);
    int id = 0;
    for(i = 1; i <= n; ) {
        for(j = i; S[sa[j]].y - S[sa[j]].x == S[sa[j + 1]].y - S[sa[j + 1]].x && j < n; ++j);
        ++id;
        for(k = i; k <= j; ++k)
            rank[sa[k]] = id;
        i = j + 1;
    }
    
    sort(S + 1, S + n + 1);
    for(i = 1; i <= n; ++i)
        change[S[i].lab] = i;
    
    memset(A, 0, sizeof(A));
    for(i = 1; i <= n; ++i) {
        int get = ask(rank[S[i].lab]);
        if (get != 0)
            E[++top] = Edge(S[i].lab, get, _abs(x[S[i].lab] - x[get]) + _abs(y[S[i].lab] - y[get]));
        modify(rank[S[i].lab], S[i].lab);
    }
}

int root[N];
void reset() {
    for(int i = 1; i <= n; ++i)
        root[i] = i;
}
int find(int x) {
    int q = x, tmpq;
    for(; x != root[x]; x = root[x]);
    for(; q != x; q = tmpq)
        tmpq = root[q], root[q] = x;
    return x;
}
long long Kruskal() {
    sort(E + 1, E + top + 1);
    reset();
    register int i;
    int ra, rb, intree = 0;
    long long res = 0;
    for(i = 1; i <= top; ++i) {
        ra = find(E[i].from);
        rb = find(E[i].to);
        if (ra != rb) {
            root[ra] = rb;
            res += E[i].len;
            if (++intree == n - 1)
                return res;
        }
    }
    return -1;
}

int main() {
    n = getint();
    register int i;
    for(i = 1; i <= n; ++i)
        x[i] = getint(), y[i] = getint();
        
    S[0].x = S[0].y = 0x3f3f3f3f;
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(x[i], y[i], i);
    AddEdge();
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(y[i], x[i], i);
    AddEdge();
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(-y[i], x[i], i);
    AddEdge();
    
    for(i = 1; i <= n; ++i)
        S[i] = Node(x[i], -y[i], i);
    AddEdge();
    
    printf("%lld", Kruskal());
    
    return 0;
}
comments powered by Disqus