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|)，比如下图所示：
~~~~) 设：Ax_0,y_0),Bx_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]°) 时可通过坐标变化到对应区域，其他区域可以由该点左边的点向其连边。
~~~~) 首先，设当前考虑的点为 Ax_0,y_0)) ，其中任意一个在对应区域内的点为 Bx_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 mpa,b) make_paira,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){}
nodeint U,int W){u=U,w=W;}
};
priority_queue<node> Q;
bool vis[100005];
int n,m,dis[100005],Val[100005];
void primint s)
{
memsetdis,127,sizeofdis));
ans=0,tot=0;
while!Q.empty)) Q.pop);
Q.pushnodes,0));
dis[s]=0;
while!Q.empty)&&tot<n)
{
int u=Q.top).u,w=Q.top).w;
Q.pop);
ifvis[u]) continue;
tot++;ans+=w;vis[u]=1;
forint i=0;i<G[u].size);i++)
{
int v=G[u][i].first,d=G[u][i].second;
ifd<dis[v]) dis[v]=d,Q.pushnodev,dis[v]));
}
}
}
inline int Absint x){return x>0?x:-x;}
struct Point{
int x,y,id;
}P[100005];
struct BIT{
int val,pos;
}Tr[100005];
inline int lowbitint x){return x&-x);}
void addint x,int val,int p)
{
for;x;x-=lowbitx)) ifTr[x].val>val) Tr[x].val=val,Tr[x].pos=p;
}
int queryint x)
{
int Minn=1e9,ret=-233;
for;x<=n;x+=lowbitx)) ifTr[x].val<Minn) Minn=Tr[x].val,ret=Tr[x].pos;
return ret;
}
bool cmpPoint x,Point y){return x.x!=y.x?x.x<y.x:x.y<y.y;}
int GetDisint i,int j)
{
return AbsP[i].x-P[j].x)+AbsP[i].y-P[j].y);
}
int main) {
int id=0;
whilescanf"%d",&n)&&n)
{
forint 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;
forint Area=1;Area<=4;Area++)
{
ifArea==2) forint i=1;i<=n;i++) swapP[i].x,P[i].y);
ifArea==3) forint i=1;i<=n;i++) P[i].x*=-1;
ifArea==4) forint i=1;i<=n;i++) swapP[i].x,P[i].y);
sortP+1,P+1+n,cmp);
forint i=1;i<=n;i++) Val[i]=P[i].y-P[i].x,Tr[i].val=1e9,Tr[i].pos=-233;
sortVal+1,Val+1+n);
int cnt=uniqueVal+1,Val+1+n)-Val-1;
forint i=n;i>=1;i--)
{
int p=lower_boundVal+1,Val+1+cnt,P[i].y-P[i].x)-Val+1;
int pos=queryp);
ifpos!=-233) G[P[i].id].push_backmpP[pos].id,GetDisi,pos))),G[P[pos].id].push_backmpP[i].id,GetDisi,pos)));
addp,P[i].x+P[i].y,i);
}
}
prim1);
printf"Case %d: Total Weight = %d
",++id,ans);
}
return 0;
}