POJ－3241－Object Clustering

ACM模版

曼哈顿最小生成树

POJ 3241 Object Clustering

曼哈顿距离

    简单说，他指两点之间的横纵坐标的差的绝对值之和。

题意

    查找平面上的点的曼哈顿距离最小生成树的第n－k小边的长度，点数在100000以内。

解析

    对于曼哈顿距离的最小生成树，朴素算法需要建立n^(n - 1)条边进行kruskal算法处理，这样子做一定会TLE的。所以需要做特殊的优化，将边数优化为4 * n条。
    这里的优化涉及到一个与曼哈顿相关的性质：以任一一个点为端点，将平面分为八块，每块占45度角，那么在生成树的最优解中，每个块与这个点至多有一条边，即一个点最多分别向八个方向最近的点连接一条边，一条边两个点共用，所以最后边数为4 * n。

代码C++

#include <iostream>
#include <algorithm>

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

struct Point
{
    int x;
    int y;
    int id;
}poi[MAXN];

bool cmp(Point a, Point b)
{
    if (a.x != b.x)
    {
        return a.x < b.x;
    }
    else
    {
        return a.y < b.y;
    }
}

//树状数组，找y - x大于当前的，但是y + x最小的
struct BIT
{
    int minVal;
    int pos;
    void init()
    {
        minVal = INF;
        pos = -1;
    }
}bit[MAXN];

//所有有效边
struct Edge
{
    int u;
    int v;
    int d;
}edge[MAXN << 2];

bool cmpEdge(Edge a, Edge b)
{
    return a.d < b.d;
}

int tot;
int n;
int F[MAXN];

int find(int x)
{
    if (F[x] == -1)
    {
        return x;
    }
    else
    {
        return F[x] = find(F[x]);
    }
}

void addEdge(int u, int v, int d)
{
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot++].d = d;
    return ;
}

int lowbit(int x)
{
    return x & (-x);    //???
}

//更新bit
void update(int i, int val, int pos)
{
    while (i > 0)
    {
        if (val < bit[i].minVal)
        {
            bit[i].minVal = val;
            bit[i].pos = pos;
        }
        i -= lowbit(i);
    }
    return ;
}

//查询[i, m]的最小值位置
int ask(int i, int m)
{
    int minVal = INF;
    int pos = -1;
    while (i <= m)
    {
        if (bit[i].minVal < minVal)
        {
            minVal = bit[i].minVal;
            pos = bit[i].pos;
        }
        i += lowbit(i);
    }
    return pos;
}

int dist(Point a, Point b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

void ManhattanMinimumSpanningTree(int n, Point p[])
{
    int a[MAXN], b[MAXN];
    tot = 0;
    for (int dir = 0; dir < 4; dir++)
    {
        //变换4种坐标
        if (dir == 1 || dir == 3)
        {
            for (int i = 0; i < n; i++)
            {
                std::swap(p[i].x, p[i].y);
            }
        }
        else if (dir == 2)
        {
            for (int i = 0; i < n; i++)
            {
                p[i].x = -p[i].x;
            }
        }
        std::sort(p, p + n, cmp);
        for (int i = 0; i < n; i++)
        {
            a[i] = b[i] = p[i].y - p[i].x;
        }
        std::sort(b, b + n);
        int m = (int)(std::unique(b, b + n) - b);
        for (int i = 1; i <= m; i++)
        {
            bit[i].init();
        }
        for (int i = n - 1; i >= 0; i--)
        {
            int pos = (int)(std::lower_bound(b, b + m, a[i]) - b + 1);
            int ans = ask(pos, m);
            if (ans != -1)
            {
                addEdge(p[i].id, p[ans].id, dist(p[i], p[ans]));
            }
            update(pos, p[i].x + p[i].y, i);
        }
    }
    return ;
}

int solve(int k)
{
    ManhattanMinimumSpanningTree(n, poi);
    memset(F, -1, sizeof(F));
    std::sort(edge, edge + tot, cmpEdge);
    for (int i = 0; i < tot; i++)
    {
        int u = edge[i].u;
        int v = edge[i].v;
        int tOne = find(u);
        int tTwo = find(v);
        if (tOne != tTwo)
        {
            F[tOne] = tTwo;
            k--;
            if (k == 0)
            {
                return edge[i].d;
            }
        }
    }
    return -1;
}

int main(int argc, const char * argv[])
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int k;
    while ((std::cin >> n >> k) && n)
    {
        for (int i = 0; i < n; i++)
        {
            std::cin >> poi[i].x >> poi[i].y;
            poi[i].id = i;
        }
        std::cout << solve(n - k) << std::endl;
    }

    return 0;
}