老oj曼哈顿最小生成树

Description

平面坐标系xOy内，给定n个顶点V = (x , y)。对于顶点u、v，u与v之间的距离d定义为|xu – xv| + |yu – yv|
你的任务就是求出这n个顶点的最小生成树。

Input

第一行一个正整数n，表示定点个数。

接下来n行每行两个正整数x、y，描述一个顶点。

Output

只有一行，为最小生成树的边的距离和。

Sample Input

Sample Output

6

[数据约定]

对于30%的数据n <= 2000；

对于50%的数据n <= 5000；

对于100%的数据n <= 50000；

0 <= x, y <= 100000。

题解：http://blog.csdn.net/acm_cxlove/article/details/8890003
code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 50005

 #define inf 1061109567

 using namespace std;

 char ch;

 bool ok;

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 int n,m,ans=;

 struct Point{

     int x,y,d,id;

 }point[maxn],tmp[maxn];

 bool cmp1(Point a,Point b){

     if (a.x!=b.x) return a.x>b.x;

     return a.y>b.y;

 }

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

 struct Edge{

     int u,v,c;

 }edge[maxn<<];

 bool cmp2(Edge a,Edge b){return a.c<b.c;}

 int cntd,d[maxn];

 struct DATA{

     int val,pos;

     void init(){val=inf,pos=-;}

     void update(DATA b){if (val>b.val) val=b.val,pos=b.pos;}

 };

 struct bit{

     #define lowbit(x) ((x)&(-(x)))

     DATA node[maxn];

     void init(){for (int i=;i<=cntd;i++) node[i].init();}

     void insert(int x,DATA p){

         x=cntd-x+;

         for (int i=x;i<=cntd;i+=lowbit(i)) node[i].update(p);

     }

     int query(int x){

         x=cntd-x+;

         DATA ans; ans.init();

         for (int i=x;i;i-=lowbit(i)) ans.update(node[i]);

         return ans.pos;

     }

 }T;

 void prepare(){

     for (int i=;i<=n;i++) d[i]=point[i].y-point[i].x;

     sort(d+,d+n+),cntd=unique(d+,d+n+)-d-;

     for (int i=;i<=n;i++) point[i].d=lower_bound(d+,d+cntd+,point[i].y-point[i].x)-d;

     sort(point+,point+n+,cmp1);

     T.init();

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

         int u=point[i].id,v=T.query(point[i].d);

         if (v!=-) edge[++m]=(Edge){u,v,calc(tmp[u],tmp[v])};

         T.insert(point[i].d,(DATA){point[i].x+point[i].y,u});

     }

 }

 int fa[maxn];

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

 int main(){

     read(n);

     for (int i=;i<=n;i++) read(point[i].x),read(point[i].y),point[i].id=i;

     for (int i=;i<=n;i++) tmp[i]=point[i]; prepare();

     for (int i=;i<=n;i++) point[i].x=tmp[i].y,point[i].y=tmp[i].x,point[i].id=i; prepare();

     for (int i=;i<=n;i++) point[i].x=-tmp[i].y,point[i].y=tmp[i].x,point[i].id=i; prepare();

     for (int i=;i<=n;i++) point[i].x=tmp[i].x,point[i].y=-tmp[i].y,point[i].id=i; prepare();

     sort(edge+,edge+m+,cmp2);

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

     for (int i=,cnt=;i<=m&&cnt<n;i++)

         if (find(edge[i].u)!=find(edge[i].v))

             fa[find(edge[i].u)]=find(edge[i].v),cnt++,ans+=edge[i].c;

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

     return ;

 }

秒客网

老oj曼哈顿最小生成树

相关文章