【BZOJ-2177】曼哈顿最小生成树 Kruskal + 树状数组

时间:2021-06-21 04:19:31

2177: 曼哈顿最小生成树

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 190  Solved: 77
[Submit][Status][Discuss]

Description

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

Input

第一行一个正整数n,表示定点个数。 
接下来n行每行两个正整数x、y,描述一个顶点。

Output

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

Sample Input

4
1 0
0 1
0 -1
-1 0

Sample Output

6

HINT

对于100%的数据n <= 50000;
0 <= x, y <= 100000。

Source

Solution

曼哈顿距离最小生成树裸题

那么来说一下曼哈顿距离最小生成树

首先给出$N$个点,求普通的最小生成树,Kruskal的时间复杂度是$O(MlogN)$,显然$M$的级别是$N^{2}$的,但曼哈顿距离最小生成树能做到$O(NlogN)$

先考虑最小生成树的一个性质:如果图中存在一个环,那么把环上最大边删掉,得到的与不删环的MST权和是一样的

利用这个性质,我们构建边的时候,就能大大减少边的数量

考虑现在在一个点$S$,可以从这个点为中心,把平面分成8份

【BZOJ-2177】曼哈顿最小生成树        Kruskal + 树状数组

然后我们发现,在一个象限中,点$S$至多和一个点相连的边是有用的。

先说一个自己的理解但不是很详尽的证明;

【BZOJ-2177】曼哈顿最小生成树        Kruskal + 树状数组

我们考虑,如果全都连边,大概是这样的情况,但是我们发现,$|AC|<|AB| && |CB|<|AB|$

那么考虑环切定理,这样,边AB是可以删去的,所以很容易理解每个点只需要连象限中离他最近的点即可

证明:

八个扇形区域是对称的,我们只考虑R1

把s看作原点,R1里面的点(x,y)都满足:

x≥0,

y>x.

考察R1里面两个点p和q,不失一般性设xp≤xq

1.       yp≤yq

|PQ|=xq+yq-(xp+xq)

|SP|=xp+yp

|SQ|=xq+yq

所以|PQ|=|SQ|-|SP|≤|SQ|

可见当yp≤yq时,|PQ|不是三角形SPQ的最长边。(在曼哈顿距离下的“最长”)

2.       yp>y

0≤xp≤xq≤yq<yp

|PQ|=xq-xp+yp-yq

|SP|=xp+yp

|SQ|=xq+yq

即|PQ|= (yp-xp)+(xq-yq)

因为xq≤yq,所以|PQ|≤yp-xp≤yp≤xp+yp=|SP|

也就是说,当yp>yq时,|PQ|仍然不是三角形SPQ的最长边。(曼哈顿距离意义下的“最长”)

综上,|PQ|无论如何也不可能是三角形SPQ的最长边。即:在环<s, p, q>中,最大边只可能是|SP|和|SQ|。根据“环切”性质,我们把|SP|和|SQ|中的较长边删除即可。

假设R1里面有m个顶点:P1, P2, …, Pm,假设距离s最近的点是Pk,那么只要在S和Pk之间连边即可。

所谓距离s最近的点,实际上就是xk+yk最小的点

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 100010
int N;
struct PointNode{int x,y,id;}P[MAXN];
bool cmpP(PointNode A,PointNode B) {return A.x!=B.x? A.x<B.x : A.y<B.y;}
struct UnionFind
{
int Fa[MAXN];
void Init() {for (int i=; i<=N; i++) Fa[i]=i;}
int Find(int x) {if (Fa[x]==x) return x; else return Fa[x]=Find(Fa[x]);}
bool Merge(int x,int y) {int f1=Find(x),f2=Find(y); if (f1==f2) return ; Fa[f1]=f2; return ;}
}uf;
int Dis(PointNode A,PointNode B) {return abs(A.x-B.x)+abs(A.y-B.y);}
struct EdgeNode{int to,val,from;}edge[MAXN<<];
int cnt;
void AddEdge(int u,int v,int w) {cnt++; edge[cnt].from=u; edge[cnt].to=v; edge[cnt].val=w;}
bool cmpE(EdgeNode A,EdgeNode B) {return A.val<B.val;}
int lowbit(int x) {return x&-x;}
struct BITNode{int minn,pos; void init() {minn=0x7fffffff; pos=-;}}bit[MAXN];
void Update(int x,int val,int pos)
{
for (int i=x; i; i-=lowbit(i))
if (val<bit[i].minn) bit[i].minn=val,bit[i].pos=pos;
}
int Query(int x,int M)
{
int minn=0x7fffffff,pos=-;
for (int i=x; i<=M; i+=lowbit(i))
if (bit[i].minn<minn) minn=bit[i].minn,pos=bit[i].pos;
return pos;
}
int num,Ans;
void MST()
{
int a[MAXN],b[MAXN];
for (int k=; k<=; k++)
{
if (k== || k==) for (int i=; i<=N; i++) swap(P[i].x,P[i].y);
else if (k==) for (int i=; i<=N; i++) P[i].x=-P[i].x;
stable_sort(P+,P+N+,cmpP);
for (int i=; i<=N; i++)
a[i]=b[i]=P[i].y-P[i].x;
stable_sort(b+,b+N+);
int M=unique(b+,b+N+)-b-;
for (int i=; i<=M; i++) bit[i].init();
for (int i=N; i>=; i--)
{
int pos=lower_bound(b+,b+M+,a[i])-b;
int ans=Query(pos,M);
if (ans!=-) AddEdge(P[i].id,P[ans].id,Dis(P[i],P[ans]));
Update(pos,P[i].x+P[i].y,i);
}
}
stable_sort(edge+,edge+cnt+,cmpE);
uf.Init();
for (int i=; i<=cnt; i++)
{
int u=edge[i].from,v=edge[i].to;
if (uf.Merge(u,v)) Ans+=edge[i].val,num++;
if (num==N-) break;
}
}
int main()
{
N=read();
for (int i=; i<=N; i++) P[i].x=read(),P[i].y=read(),P[i].id=i;
MST();
printf("%d\n",Ans);
return ;
}

感觉很愚蠢的代码