51Nod 1213. 二维曼哈顿距离最小生成树(RMQ+最小生成树+贪心)

日付: 10月 25, 2018

[二维曼哈顿距离最小生成树问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1213)
# Problem
二维平面上有$n$个点，构成以曼哈顿距离为边长的完全图，求最小生成树边权和。

数据范围：$1\le n \le 50000$, $1 \le x, y \le 1000000$
# Solution
实在是想不出来怎么减少边的数量于是看了题解(太弱啦)。观察可以发现很多边都是不必要的，对于三个点$A, B, C$，如果$|AB|  > |BC|$，那么$|AC|$就是无用边。如果把$A$看作原点，那么$x$轴正方向与$y=x$之间的区域中，只有与$A$曼哈顿距离最近的一个点与$A$的边是有效边。下图中，如果$B$是这个最近点，虚线上的所有点与$A$是等距的，虚线内不可能存在其他点，对于虚线外的点，可以发现$|AC| > |BC|$一定成立，可以不用考虑，对于虚线上的点，$|AC| \ge |BC|$一定成立，因此只需要选一个点就可以了。

对于其他区域的最近点，只需要坐标变换后再算一次就可以了，由于对称性，可以只算一二象限的四个区域。求最近点可以用RMQ来做，设$A$点坐标是$(x_0, y_0)$，其他某个点的坐标是$(x, y)$，如果$x \ge x_0, y  \ge y_0, y-y_0 \le x - x_0$成立，那么$(x,y)$就在$x$轴正方向与$y=x$之间，现在要最小化$y-y_0+x-x_0$。我们可以排序所有点然后倒序(保证$x \ge x_0$)遍历，维护区间最小值，键为$y-x$(离散化后)，值为$y+x$，这样每次求区间$[0, y_0-x_0]$之间最小的$(y+x)$，然后减去$y_0+x_0$就是边长。求出的最近点需要知道编号，可以用$(y+x, id)$对作为RMQ的值。因为只需要查询前缀最小值，RMQ可以用树状数组维护。

但是这样还是有一个问题，无法保证条件$y \ge y_0$，发现可以改成计算$y$轴正方向与$y=x$之间的区域解决。这样限制条件就变成了$x \ge x_0, y \ge y_0, y-y_0 \ge x - x_0$，可以看出条件1和条件3包含了条件2，条件1由倒序遍历满足，条件3只需查询的区间是$[y_0-x_0, n)$就可以满足，这里$n$表示区间大小。(如果用树状数组维护的话，可以在更新和查询时都用$n$减一下，这样就可以把后缀查询变成前缀了。

找到所有可能的边后就可以用Kruskal算法找出最小生成树。

```c++
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;

template <typename T> struct Fenwick {
    T unit;
    vector<T> V;
    Fenwick(int n, T unit): unit(unit), V(n, unit) {}
    void add(size_t i, T x) { for (; i < V.size(); i |= i + 1) V[i] = min(x, V[i]); }
    T sum(int i) { T r = unit; for (--i; i >= 0; i = (i & (i + 1)) - 1) r = min(r, V[i]); return r; }
};

struct UnionFind {
    vector<int> V;
    UnionFind(int n): V(n, -1) {}
    int root(int x) { return V[x] < 0 ? x : V[x] = root(V[x]); }
    int size(int x) { return -V[root(x)]; }
    bool same(int x, int y) { return root(x) == root(y); }
    bool unite(int x, int y) {
        x = root(x), y = root(y);
        if (x != y) {
            if (V[y] < V[x]) swap(x, y);
            V[x] += V[y], V[y] = x;
        }
        return x != y;
    }
};

int main() {
    int n;
    scanf("%d", &n);
    vector<array<int, 3>> P, E;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        P.push_back({x, y, i});
    }
    auto run = [&]() {
        sort(P.begin(), P.end());
        reverse(P.begin(), P.end());
        vector<int> C;
        for (auto &x : P) C.push_back(x[1] - x[0]);
        sort(C.begin(), C.end());
        C.erase(unique(C.begin(), C.end()), C.end());
        Fenwick<PII> fw(C.size(), PII{INT_MAX, -1});
        for (auto &p : P) {
            int pos = C.end() - lower_bound(C.begin(), C.end(), p[1] - p[0]) - 1;
            auto ma = fw.sum(pos + 1);
            fw.add(pos, {p[0] + p[1], p[2]});
            if (ma.second == -1) continue;
            E.push_back({ma.first - p[0] - p[1], ma.second, p[2]});
        }
    };
    run();
    for (auto &p : P) p[0] = -p[0];
    run();
    for (auto &p : P) p[0] = -p[0], p[1] = -p[1], swap(p[0], p[1]);
    run();
    for (auto &p : P) p[0] = -p[0];
    run();
    sort(E.begin(), E.end());
    UnionFind uf(n);
    auto ans = 0LL;
    for (auto &e : E) {
        if (uf.same(e[1], e[2])) continue;
        else uf.unite(e[1], e[2]), ans += e[0];
    }
    printf("%lld\n", ans);
    return 0;
}
```
</details>

KONGROOの基地

このブログを検索

51Nod 1213. 二维曼哈顿距离最小生成树(RMQ+最小生成树+贪心)

コメント

コメントを投稿