POJ3241 Object Clustering 曼哈顿最小生成树

题意：转换一下就是求曼哈顿最小生成树的第n-k条边

参考：莫涛大神的论文《平面点曼哈顿最小生成树》

/*

Problem: 3241        User: 96655

Memory: 920K        Time: 94MS

Language: C++        Result: Accepted

*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn=;

const int INF=0x3f3f3f3f;

const int maxm=;

int n,k,p;

struct Point

{

    int x,y,id;

    bool operator<(const Point &e)const

    {

        if(x==e.x)return y<e.y;

        return x<e.x;

    }

} point[maxn];

struct Edge

{

    int u,v,w;

    bool operator<(const Edge &e)const

    {

        return w<e.w;

    }

} edge[maxn*];

void addedge(int a,int b,int l,int r)

{

    ++p;

    edge[p].u=a;

    edge[p].v=b;

    edge[p].w=abs(l-r);

}

struct Node

{

    int len,id;

} node[(maxm+)<<];

void pushup(int rt)

{

    node[rt].len=min(node[rt*].len,node[rt*+].len);

    if(node[rt].len==node[rt*].len)node[rt].id=node[rt*].id;

    else node[rt].id=node[rt*+].id;

}

void change(int rt,int l,int r,Point tt)

{

    if(l==r)

    {

        node[rt].len=tt.x+tt.y;

        node[rt].id=tt.id;

        return;

    }

    int pos=tt.y-tt.x+;

    int m=(l+r)>>;

    if(pos<=m)change(rt*,l,m,tt);

    else change(rt*+,m+,r,tt);

    pushup(rt);

}

Node query(int rt,int l,int r,int x,int y)

{

    if(x<=l&&r<=y)

        return node[rt];

    int m=(l+r)>>;

    if(y<=m)return query(rt*,l,m,x,y);

    else if(x>m)return query(rt*+,m+,r,x,y);

    else

    {

        Node t1,t2;

        t1=query(rt*,l,m,x,y);

        t2=query(rt*+,m+,r,x,y);

        if(t1.len<t2.len)return t1;

        else return t2;

    }

}

int fa[maxn];

int find(int x)

{

    if(x==fa[x])return x;

    return fa[x]=find(fa[x]);

}

void init()

{

    for(int i=; i<(maxm<<); ++i)

        node[i].len=INF,node[i].id=-;

}

void build()

{

    sort(point+,point++n);

    init();

    for(int i=n; i>; --i)

    {

        int s=point[i].x+point[i].y;

        Node t=query(,,maxm,point[i].y-point[i].x+,maxm);

        if(t.id!=-)

            addedge(point[i].id,t.id,s,t.len);

        change(,,maxm,point[i]);

    }

}

int solve()

{

    sort(edge+,edge+p+);

    int cnt=;

    for(int i=; i<=p; ++i)

    {

        int fx=find(edge[i].u);

        int fy=find(edge[i].v);

        if(fx!=fy)

        {

            fa[fy]=fx;

            ++cnt;

            if(cnt==n-k)return edge[i].w;

        }

    }

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=; i<=n; ++i)

        scanf("%d%d",&point[i].x,&point[i].y),point[i].id=i;

    for(int i=; i<=n; ++i)

        fa[i]=i;

    p=;

    build();

    for(int i=; i<=n; ++i)

        point[i].y=-point[i].y;

    build();

    for(int i=; i<=n; ++i)

        point[i].y=-point[i].y,swap(point[i].x,point[i].y);

    build();

    for(int i=; i<=n; ++i)

        point[i].y=-point[i].y;

    build();

    printf("%d\n",solve());

    return ;

}