BZOJ 2177: 曼哈顿最小生成树

时间：2022-09-14 04:18:00

Sol

考了好几次曼哈顿最小生成树,然而一直不会打...这次终于打出来了...神tm调试了2h...好蛋疼...

首先曼哈顿最小生成树有个结论就是讲它每45度分出一个象限,对于每个点,只与每个象限中离他最近的点连线,做最小生成树,就是他们的曼哈顿最小生成树.

关于证明,先让我想想再来补.

我们的问题两个方面:为什么将平面分成8块;为什么只需要连接每块中距离最小的点.

不过好像没人稀罕说第一个问题...我自己yy了一下,感觉挺科学的...将平面分成8块的原因就是两个点计算距离的时候去掉绝对值后有8种可能.

\(Dis(A,B)=\pm (x_A-x_B)\pm (y_A-y_B)\) 这样就有4种结果,然后A,B位置可以互换,这样就是8种了...然后分成8个部分...唔...好像是这样吧..

(欢迎打脸~BZOJ 2177: 曼哈顿最小生成树)

证明:如下图,对于每三个这样的点,最小生成树显然是割掉矩形的一个角,使割掉的边尽量的大就好,最后在这个区域就只会剩下一个与它相连点,同时也是最近的一个点.

(这个也是我自己yy的qwq.可能不太完整,甚至是错误的...不过欢迎来打脸...BZOJ 2177: 曼哈顿最小生成树)

BZOJ 2177: 曼哈顿最小生成树

因为边数是 \(4n\) 的,所以用Kruskal做最小生成树的复杂度 \(O(nlogn)\) .

至于8个方向只需要选择一个半平面连线就可以了,因为边是双向的.

这样就需要处理4块,这四块可以由一块通过关于y轴对称,关于直线x=y对称和关于y轴对称后再关于x=y对称.

PS:代码调试宛如智障.

Code

#include<cstdio>

#include<cstring>

#include<vector>

#include<utility>

#include<queue>

#include<algorithm>

#include<iostream>

using namespace std;

#define mpr(a,b) make_pair(a,b)

const int N = 50005;

int n,ans;

struct seat{ int x,y,id; }a[N],b[N];

bool operator < (const seat &a,const seat &b){ return a.x==b.x?a.y>b.y:a.x>b.x; }

int d[N<<1],id[N<<1],cnt,ys[N];

struct Edge{ int u,v,w; };

bool operator < (const Edge &a,const Edge &b){ return a.w>b.w; }

priority_queue<Edge> q;

int f[N];

inline int in(int x=0,char ch=getchar(),int v=1){

    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();if(ch=='-') v=-1,ch=getchar();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*v; }

//int cmpx(const seat &a,const seat &b){ return a.x==b.x?a.x<b.x:a.y<b.y; }

//int cmpxy(const seat &a,const seat &b){ return a.y-a.x<b.y-b.x; }

inline int abs(int x){ return x<0?-x:x; }

int find(int x){ return f[x]==x?x:f[x]=find(f[x]); }

void Add_Edge(int u,int v){

    int dis=abs(a[u].x-a[v].x)+abs(a[u].y-a[v].y);

    q.push((Edge){ u,v,dis });

}

void Add(int x,int v,int pos){

    for(;x;x-=x&-x) if(d[x]>v) d[x]=v,id[x]=pos;

}

int Query(int x){

    int minv=0x7f7f7f7f,pos=-1;

    for(;x<=cnt;x+=x&-x) if(d[x]<minv) minv=d[x],pos=id[x];

    return pos;

}

void out(seat a){ cout<<a.x<<" "<<a.y<<" "<<a.id<<endl<<"***************\n"; }

void Build(){

/*        Part1 x1>x0&&y1-x1>y0-x0     dis=(x1+y1)-(x0+y0)         */

    memset(d,0x7f,sizeof(d)),memset(id,-1,sizeof(id)),memset(ys,0,sizeof(ys));cnt=0;

    for(int i=1;i<=n;i++) b[i]=a[i];

//  for(int i=1;i<=n;i++) out(a[i]);

    sort(b+1,b+n+1);

//  for(int i=1;i<=n;i++) out(b[i]);

    for(int i=1;i<=n;i++) ys[i]=b[i].y-b[i].x;

    sort(ys+1,ys+n+1);

    cnt=unique(ys+1,ys+n+1)-ys-1;

//  cout<<cnt<<endl;

//  for(int i=1;i<=cnt;i++) cout<<ys[i]<<" ";cout<<endl;

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

        int x=lower_bound(ys+1,ys+cnt+1,b[i].y-b[i].x)-ys;

        int pos=Query(x);

        if(~pos) Add_Edge(b[i].id,pos);

//      cout<<b[i].id<<"-->"<<pos<<endl;

        Add(x,b[i].x+b[i].y,b[i].id);

    }

/*        Part2 swap(x,y)                                            */

    memset(d,0x7f,sizeof(d)),memset(id,-1,sizeof(id)),memset(ys,0,sizeof(ys));cnt=0;

    for(int i=1;i<=n;i++) b[i].y=a[i].x,b[i].x=a[i].y,b[i].id=a[i].id;

    sort(b+1,b+n+1);

//  for(int i=1;i<=n;i++) out(b[i]);

    for(int i=1;i<=n;i++) ys[i]=b[i].y-b[i].x;

    sort(ys+1,ys+n+1);

    cnt=unique(ys+1,ys+n+1)-ys-1;

//  cout<<cnt<<endl;

//  for(int i=1;i<=cnt;i++) cout<<ys[i]<<" ";cout<<endl;

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

        int x=lower_bound(ys+1,ys+cnt+1,b[i].y-b[i].x)-ys;

        int pos=Query(x);

        if(~pos) Add_Edge(b[i].id,pos);

//      cout<<b[i].id<<"-->"<<pos<<endl;

        Add(x,b[i].x+b[i].y,b[i].id);

    }

/*        Part3 y=-y                                                 */

    memset(d,0x7f,sizeof(d)),memset(id,-1,sizeof(id)),memset(ys,0,sizeof(ys));cnt=0;

    for(int i=1;i<=n;i++) b[i]=a[i],b[i].y=-b[i].y;

    sort(b+1,b+n+1);

//  for(int i=1;i<=n;i++) out(b[i]);

    for(int i=1;i<=n;i++) ys[i]=b[i].y-b[i].x;

    sort(ys+1,ys+n+1);

    cnt=unique(ys+1,ys+n+1)-ys-1;

//  cout<<cnt<<endl;

//  for(int i=1;i<=cnt;i++) cout<<ys[i]<<" ";cout<<endl;

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

        int x=lower_bound(ys+1,ys+cnt+1,b[i].y-b[i].x)-ys;

        int pos=Query(x);

        if(~pos) Add_Edge(b[i].id,pos);

//      cout<<b[i].id<<"-->"<<pos<<endl;

        Add(x,b[i].x+b[i].y,b[i].id);

    }

/*        Part4 swap(x,y) y=-y                                       */

    memset(d,0x7f,sizeof(d)),memset(id,-1,sizeof(id)),memset(ys,0,sizeof(ys));cnt=0;

    for(int i=1;i<=n;i++) b[i].x=-a[i].y,b[i].y=a[i].x,b[i].id=a[i].id;

    sort(b+1,b+n+1);

//  for(int i=1;i<=n;i++) out(b[i]);

    for(int i=1;i<=n;i++) ys[i]=b[i].y-b[i].x;

    sort(ys+1,ys+n+1);

    cnt=unique(ys+1,ys+n+1)-ys-1;

//  cout<<cnt<<endl;

//  for(int i=1;i<=cnt;i++) cout<<ys[i]<<" ";cout<<endl;

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

        int x=lower_bound(ys+1,ys+cnt+1,b[i].y-b[i].x)-ys;

        int pos=Query(x);

        if(~pos) Add_Edge(b[i].id,pos);

//      cout<<b[i].id<<"-->"<<pos<<endl;

        Add(x,b[i].x+b[i].y,b[i].id);

    }

/*         MST                                                       */

    for(int i=1;i<=n;i++) f[i]=i;

    for(int k=1;!q.empty();){

        Edge e=q.top();q.pop();

        int u=e.u,v=e.v;

        int f1=find(u),f2=find(v);

        if(f1!=f2) k++,f[f2]=f1,ans+=e.w;

        if(k>=n) break;

    }cout<<ans<<endl;

}

int main(){

//  freopen("in.in","r",stdin);

//  freopen("out.out","w",stdout);

    n=in();for(int i=1;i<=n;i++) a[i].x=in(),a[i].y=in(),a[i].id=i;

    Build();

    return 0;

}

　　

相关文章