老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：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 50005
 7 #define inf 1061109567
 8 using namespace std;
 9 char ch;
10 bool ok;
11 void read(int &x){
12     for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;
13     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
14     if (ok) x=-x;
15 }
16 int n,m,ans=0;
17 struct Point{
18     int x,y,d,id;
19 }point[maxn],tmp[maxn];
20 bool cmp1(Point a,Point b){
21     if (a.x!=b.x) return a.x>b.x;
22     return a.y>b.y;
23 }
24 int calc(Point a,Point b){return abs(a.x-b.x)+abs(a.y-b.y);}
25 struct Edge{
26     int u,v,c;
27 }edge[maxn<<2];
28 bool cmp2(Edge a,Edge b){return a.c<b.c;}
29 int cntd,d[maxn];
30 struct DATA{
31     int val,pos;
32     void init(){val=inf,pos=-1;}
33     void update(DATA b){if (val>b.val) val=b.val,pos=b.pos;}
34 };
35 struct bit{
36     #define lowbit(x) ((x)&(-(x)))
37     DATA node[maxn];
38     void init(){for (int i=1;i<=cntd;i++) node[i].init();}
39     void insert(int x,DATA p){
40         x=cntd-x+1;
41         for (int i=x;i<=cntd;i+=lowbit(i)) node[i].update(p);
42     }
43     int query(int x){
44         x=cntd-x+1;
45         DATA ans; ans.init();
46         for (int i=x;i;i-=lowbit(i)) ans.update(node[i]);
47         return ans.pos;
48     }
49 }T;
50 void prepare(){
51     for (int i=1;i<=n;i++) d[i]=point[i].y-point[i].x;
52     sort(d+1,d+n+1),cntd=unique(d+1,d+n+1)-d-1;
53     for (int i=1;i<=n;i++) point[i].d=lower_bound(d+1,d+cntd+1,point[i].y-point[i].x)-d;
54     sort(point+1,point+n+1,cmp1);
55     T.init();
56     for (int i=1;i<=n;i++){
57         int u=point[i].id,v=T.query(point[i].d);
58         if (v!=-1) edge[++m]=(Edge){u,v,calc(tmp[u],tmp[v])};
59         T.insert(point[i].d,(DATA){point[i].x+point[i].y,u});
60     }
61 }
62 int fa[maxn];
63 int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
64 int main(){
65     read(n);
66     for (int i=1;i<=n;i++) read(point[i].x),read(point[i].y),point[i].id=i;
67     for (int i=1;i<=n;i++) tmp[i]=point[i]; prepare();
68     for (int i=1;i<=n;i++) point[i].x=tmp[i].y,point[i].y=tmp[i].x,point[i].id=i; prepare();
69     for (int i=1;i<=n;i++) point[i].x=-tmp[i].y,point[i].y=tmp[i].x,point[i].id=i; prepare();
70     for (int i=1;i<=n;i++) point[i].x=tmp[i].x,point[i].y=-tmp[i].y,point[i].id=i; prepare();
71     sort(edge+1,edge+m+1,cmp2);
72     for (int i=1;i<=n;i++) fa[i]=i;
73     for (int i=1,cnt=0;i<=m&&cnt<n;i++)
74         if (find(edge[i].u)!=find(edge[i].v)) 
75             fa[find(edge[i].u)]=find(edge[i].v),cnt++,ans+=edge[i].c;
76     printf("%d
",ans);
77     return 0;
78 }