POJ - 3241 Object Clustering(莫队算法/曼哈顿最小生成树)

待我称王封你为后i 2022-06-07 04:54 92阅读 0赞

[点我看题][Link 1]

题意:给出n个点,第i个点的坐标为(xi,yi),求这n个点形成的曼哈顿最小生成树的第k大边.

分析:曼哈顿最小生成树的模板题([平面曼哈顿最小生成树的详解][Link 2]

参考代码:

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    #define INF 0x3f3f3f3f
    const int maxn = 1e4+10;
    const int maxm = 2e3+10;
    int n,k;
    int tree[maxm],pos[maxm];
    struct Point{
        int x,y,id;
        int xsy;
    };
    Point point[maxn],p[maxn];
    struct Edge{
        int u,v,w;
        Edge(){}
        Edge( int uu, int vv, int ww)
        {
            u = uu, v = vv, w = ww;
        }
        bool operator < ( const Edge &e)const
        {
            return w < e.w;
        }
    };
    vector<Edge> e;
    int fa[maxn];
    
    bool cmpx( Point p1, Point p2)
    {
        if( p1.x != p2.x)
            return p1.x > p2.x;
        return p1.y > p2.y;
    }
    
    bool cmpxsy( Point p1, Point p2)
    {
        return p1.xsy < p2.xsy;
    }
    
    int dist( Point p1, Point p2)
    {
        return abs(p1.x-p2.x)+abs(p1.y-p2.y);
    }
    
    inline int lowbit( int x)
    {
        return x&-x;
    }
    
    void add( int i, int val, int id)
    {
        while( i < maxm)
        {
            if( tree[i] > val)
            {
                tree[i] = val;
                pos[i] = id;
            }
            i += lowbit(i);
        }
    }
    
    int query( int i)
    {
        int id = -1, val = INF;
        while( i > 0)
        {
            if( tree[i] < val)
            {
                val = tree[i];
                id = pos[i];
            }
            i -= lowbit(i);
        }
        return id;
    }
    
    void Manhaton( int n)
    {
        for( int i = 0; i < n; i++)
            point[i].xsy = point[i].x-point[i].y;
        sort(point,point+n,cmpxsy);
        int now = 0, pre = -INF;
        for( int i = 0; i < n; i++)
        {
            if( pre != point[i].xsy)
            {
                now++;
                pre = point[i].xsy;
            }
            point[i].xsy = now;
        }
        sort(point,point+n,cmpx);
        for( int i = 1; i < maxm; i++)
            tree[i] = INF, pos[i] = -1;
        for( int i = 0; i < n; i++)
        {
            int u = point[i].id;
            int v = query(point[i].xsy);
            if( v != -1)
                e.push_back(Edge(u,v,dist(p[u],p[v])));
            add(point[i].xsy,point[i].x+point[i].y,u);
        }
    }
    
    void BuildEdge( int n)
    {
        e.clear();
        for( int cnt = 0; cnt < 4; cnt++)
        {
            for( int i = 0; i < n; i++)
                point[i] = p[i];
            for( int i = 0; i < n; i++)
            {
                if(cnt == 1)
                    swap(point[i].x,point[i].y);
                else if( cnt == 2)
                    point[i].y = -point[i].y;
                else if( cnt == 3)
                {
                    swap(point[i].x,point[i].y);
                    point[i].y = -point[i].y;
                }
            }
            Manhaton(n);
        }
    }
    
    int find( int x)
    {
        if( x == fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }
    
    int MST( int n, int k)
    {
        if( n <= k)
            return 0;
        for( int i = 0; i < n; i++)
            fa[i] = i;
        sort(e.begin(),e.end());
        int sz = e.size();
        for( int i = 0; i < sz; i++)
        {
            int u = find(e[i].u);
            int v = find(e[i].v);
            if( u == v)
                continue;
            fa[u] = v;
            n--;
            if( n == k)
                return e[i].w;
        }
    }
    
    int main()
    {
        while( ~scanf("%d%d",&n,&k))
        {
            for( int i = 0; i < n; i++)
            {
                scanf("%d%d",&p[i].x,&p[i].y);
                p[i].id = i;
            }
            BuildEdge(n);
            printf("%d\n",MST(n,k));
        }
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3241
[Link 2]: https://wenku.baidu.com/view/977fab114431b90d6c85c760.html