Another Minimum Spanning Tree 题解
(~~~~) 题目名字这么长其实直接叫 最小曼哈顿距离生成树 就好了
(sf Description)
(~~~~) 给出 (n （1leq nleq 10^5）) 个平面直角坐标系内的点。点之间的距离为他们的曼哈顿距离。求其最小生成树。
(sf Hint)
(~~~~) 对于如图所示的 (A) 点，其在最小生成树里只会直接连接阴影区域内最多一个点。
(sf Solution)
(~~~~) 下文中，若对一条线段加 (||) ，则表示其曼哈顿距离。
(~~~~) 首先来证明上面的 (sf {Hint}) 及一个衍伸结论：(A) 点必定连向该区域内曼哈顿距离下距离它最近的点 ：
(~~~~) 不妨设 (A,B) 在相对点 (O) 的极角为 ([45,90]°) 的区域内，且 (|OA|<|OB|)，比如下图所示：
(~~~~) 设：(A(x_0,y_0),B(x_1,y_1)) 。且由于其相对点 (O) 的极角范围可知：(x_0,x_1>0,y_0-x_0,y_1-x_1>0)，故 (|AO|=x_0+y_0,|BO|=x_1+y_1)。下面分情况来讨论：
-
若 (A) 在 (B) 的右上方，则不可能有 (|OA|<|OB|) ；
-
若 (A) 在 (B) 的右上方或上方，则 (|AB|=x_1-x_0+y_0-y_1) ，(|BO|-|AB|=x_0-y_0+2y_1) ，由于 (y_0>y_1>x_1>x_0>0) ，若 (|BO|<|AB|) 则 (x_0+2y_1<y_0)，故代入 (|AO|=x_0+y_0>2x_0+2y_1)，(|BO|=x_1+y_1<2y_1<2x_0+2y_1<|AO|) ，推得矛盾，故 (|BO|geq |AB|) ，则连接 (AO、AB) 的总代价必然 (geq) 连接 (AO、AB) 的总代价；
-
若 (A) 在 (B) 的右下方或右方，则同 2 进行讨论；
-
若 (A) 在 (B) 的左下方，则 (|OA|+|AB|=|OB|) ，同理连接 (AO、AB) 的总代价必然 连接 >(AO、AB) 的总代价。
(~~~~) 因此我们需要做的就是对每个点选择区域内距离最近的点连双向边。
(~~~~) 下面考虑一些细节，依然按照极角范围在 ([45,90]°) 考虑，若在 ([-90,45]°) 时可通过坐标变化到对应区域，其他区域可以由该点左边的点向其连边。
(~~~~) 首先，设当前考虑的点为 (A(x_0,y_0)) ，其中任意一个在对应区域内的点为 (B(x_1,y_1)) ，则：
- 显然有 (x_0<x_1,y_0<y_1) ；
- (AB) 连线的斜率必定大于等于一、三象限角平分线（即直线 (y=x) ），则 (dfrac{y_1-y_0}{x_1-x_0}geq 1) ，化简可得 (y_1-x_1>y_0-x_0) （这里并不用舍去 (x_0=x_1)）；
- 求到 (|AB|=x_1-x_0+y_1-y_0) 最小，由于对于 (A) 来说 (x_0,y_0) 一定，故求 (x_1+y_1) 最小。
(~~~~)
(~~~~) 代码实现时，按横坐标排序从后往前考虑，用 BIT 维护满足第二条限制的最小的 (x+y) 即可。
(~~~~) 则建完图后得到一张 (n) 个点，(4n) 条边的图，直接跑任意最小生成树算法即可。
(~~~~) 简单提一下坐标变化：
- 若极角在 ([0,45]°) ，则与直线 (y=x) 对称；
- 若极角在 ([-45,0]°)，则与直线 (y=x) 对称后再与 (y) 轴对称；
- 若极角在 ([-90,-45]°)，则与 (y) 轴对称。
(sf Code)
查看代码
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define mp(a,b) make_pair(a,b)
using namespace std;
int ans,tot;
vector< pair<int,int> > G[100005];
struct node{
int u,w;
bool operator <(const node &x) const{return w>x.w;}
node(){}
node(int U,int W){u=U,w=W;}
};
priority_queue<node> Q;
bool vis[100005];
int n,m,dis[100005],Val[100005];
void prim(int s)
{
memset(dis,127,sizeof(dis));
ans=0,tot=0;
while(!Q.empty()) Q.pop();
Q.push(node(s,0));
dis[s]=0;
while(!Q.empty()&&tot<n)
{
int u=Q.top().u,w=Q.top().w;
Q.pop();
if(vis[u]) continue;
tot++;ans+=w;vis[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i].first,d=G[u][i].second;
if(d<dis[v]) dis[v]=d,Q.push(node(v,dis[v]));
}
}
}
inline int Abs(int x){return x>0?x:-x;}
struct Point{
int x,y,id;
}P[100005];
struct BIT{
int val,pos;
}Tr[100005];
inline int lowbit(int x){return x&(-x);}
void add(int x,int val,int p)
{
for(;x;x-=lowbit(x)) if(Tr[x].val>val) Tr[x].val=val,Tr[x].pos=p;
}
int query(int x)
{
int Minn=1e9,ret=-233;
for(;x<=n;x+=lowbit(x)) if(Tr[x].val<Minn) Minn=Tr[x].val,ret=Tr[x].pos;
return ret;
}
bool cmp(Point x,Point y){return x.x!=y.x?x.x<y.x:x.y<y.y;}
int GetDis(int i,int j)
{
return Abs(P[i].x-P[j].x)+Abs(P[i].y-P[j].y);
}
int main() {
int id=0;
while(scanf("%d",&n)&&n)
{
for(int i=1;i<=n;i++) scanf("%d %d",&P[i].x,&P[i].y),G[i].clear(),vis[i]=dis[i]=0,P[i].id=i;
for(int Area=1;Area<=4;Area++)
{
if(Area==2) for(int i=1;i<=n;i++) swap(P[i].x,P[i].y);
if(Area==3) for(int i=1;i<=n;i++) P[i].x*=-1;
if(Area==4) for(int i=1;i<=n;i++) swap(P[i].x,P[i].y);
sort(P+1,P+1+n,cmp);
for(int i=1;i<=n;i++) Val[i]=P[i].y-P[i].x,Tr[i].val=1e9,Tr[i].pos=-233;
sort(Val+1,Val+1+n);
int cnt=unique(Val+1,Val+1+n)-Val-1;
for(int i=n;i>=1;i--)
{
int p=lower_bound(Val+1,Val+1+cnt,P[i].y-P[i].x)-Val+1;
int pos=query(p);
if(pos!=-233) G[P[i].id].push_back(mp(P[pos].id,GetDis(i,pos))),G[P[pos].id].push_back(mp(P[i].id,GetDis(i,pos)));
add(p,P[i].x+P[i].y,i);
}
}
prim(1);
printf("Case %d: Total Weight = %d
",++id,ans);
}
return 0;
}