bzoj2177 曼哈顿最小生成树

题目描述

平面坐标系xOy内,给定n个顶点V = (x , y)。对于顶点u、v,u与v之间的距离d定义为|xu – xv| + |yu – yv|

你的任务就是求出这n个顶点的最小生成树。

输入格式

第一行一个正整数n,表示定点个数。

接下来n行每行两个正整数x、y,描述一个顶点。

输出格式

只有一行,为最小生成树的边的距离和。

样例输入

4
1 0
0 1
0 -1
-1 0

样例输出

6

说明

对于100%的数据n <= 50000;

0 <= x, y <= 100000。


分析

曼哈顿距离最小生成树。

有一个结论:以点$u$为原点建系,用$x$轴、$y$轴、$y=x$、$y=-x$把平面分成$8$部分,那么对于每一部分中的点,$u$只可能与最近的点连边。

证明用不等式搞一搞可以搞出来。

这样边数就从$O(n^2)$变成了$O(n)$,可以用Kruscal$O(n\log n)$求最小生成树。

现在主要是如何找到每个部分中最近的点。

我们先做$x\ge 0$、$y\ge x$构成的部分(其他几个部分可以通过坐标变换转化成这种情况)。

对于每个点$(x,y)$,我们要寻找满足$x_i\ge x$且$y_i-x_i\ge y-x$的$x_i+y_i$最小的点。

因为可以离线,我们按$x$从大到小加点,那么就变成一维区间最小值,用线段树解决即可。而且此题只需求后缀最小值,可以用树状数组。

另外,因为边是双向的,只需要做$4$个部分。

这个算法似乎可以用来做莫队(复杂度理论最优,但不如分块好写)。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 50050;
const int INF = 0x3f3f3f3f;

int n;

struct Point {
    int x, y;
    int id;

    bool operator < (const Point &t) const {
        if (x != t.x) return x < t.x;
        return y < t.y;
    }
} a[N];

namespace MST {
    struct DS {
        int fa[N];

        DS() {
            for (int i = 0; i < N; i++)
                fa[i] = i;
        }

        int find(int x) {
            if (fa[x] != x) fa[x] = find(fa[x]);
            return fa[x];
        }
    } ds;

    struct Edge {
        int u, v, w;

        bool operator < (const Edge &t) const {
            return w < t.w;
        }
    } e[N*8];

    int m;

    void add(int u, int v, int w) {
        e[++m] = (Edge){u, v, w};
    }

    ll kruscal() {
        std::sort(e+1, e+m+1);
        ll sum = 0;
        for (int i = 1, cnt = 0; i <= m && cnt < n-1; i++) {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            int fu = ds.find(u), fv = ds.find(v);
            if (fu == fv) continue;
            ds.fa[fu] = fv;
            sum += w;
            cnt++;
        }
        return sum;
    }
}

namespace BIT {
    int n;
    int a[N], b[N];

    int lb(int x) {
        return x & -x;
    }

    void init(int _n) {
        n = _n;
        memset(a, 0x3f, sizeof a);
        memset(b, 0, sizeof b);
    }

    void add(int pos, int val, int id) {  // 在pos处对val取min,点编号为id 
        pos = n-pos+1;
        for (int i = pos; i <= n; i += lb(i)) {
            if (val < a[i]) {
                a[i] = val;
                b[i] = id;
            }
        }
    }

    int query(int pos) {  // 求位置>=pos的最小值点编号 
        pos = n-pos+1;
        int rtn = 0, mi = INF;
        for (int i = pos; i; i -= lb(i)) {
            if (a[i] < mi) {
                mi = a[i];
                rtn = b[i];
            }
        }
        return rtn;
    }
}

int d[N];
int dif;

void getDisc() {
    static int disc[N];
    for (int i = 1; i <= n; i++)
        disc[i] = d[i];
    std::sort(disc+1, disc+n+1);
    dif = std::unique(disc+1, disc+n+1) - 1 - disc;
    for (int i = 1; i <= n; i++)
        d[i] = std::lower_bound(disc+1, disc+dif+1, d[i]) - disc;
}

int getDis(int u, int v) {
    return abs(a[u].x - a[v].x) + abs(a[u].y - a[v].y);
}

void solve() {
    std::sort(a+1, a+n+1);
    for (int i = 1; i <= n; i++)
        d[i] = a[i].y - a[i].x;
    getDisc();
    BIT::init(dif);
    for (int i = n; i >= 1; i--) {
        int t = BIT::query(d[i]);
        if (t) MST::add(a[i].id, a[t].id, getDis(i, t));
        BIT::add(d[i], a[i].x+a[i].y, i);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].id = i;
    }
    for (int i = 1; i <= 4; i++) {
        if (i == 2 || i == 4) {
            for (int j = 1; j <= n; j++)
                std::swap(a[j].x, a[j].y);
        }
        if (i == 3) {
            for (int j = 1; j <= n; j++)
                a[j].x *= -1;
        }
        solve();
    }
    printf("%lld\n", MST::kruscal());
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论