P2076 曼哈顿距离最小生成树 题解

· · 题解

思路分析：

让求最小生成树，我只会 Kruskal，但是 Kruskal 的复杂度是 O(m\log m)，完全图中达到了 O(n^2\log n)，完全无法接受，那么我们考虑将边数降低到 O(n) 的级别。

既然是边权是曼哈顿距离，那么我们只需要考虑“最近”的点连边。避免重边我们每个节点只向右连边。怎么样的点是“最近”的？分别以每个点为原点建坐标系，可以将平面分成如下四个部分：

有一个结论是在每部分中只需贪心地找到最近的一个点进行连边即可，证明参考 FFTotoro 大佬的题解，这里没有更好的证法，就没必要赘述了。

接下来如何贪心地找到曼哈顿距离最小的点？以 S1 这部分为例，当我们枚举到 u 这条边时，要找到 v 满足 x_v>x_u,y_v-x_v>y_u-x_u，且 (x_v-x_u)+(y_v-y_u) 最小，即最小化 x_v+y_v。转化为了二维偏序问题，那么就先按 x-y 降序排序，x 为下标 x+y 为值，用树状数组维护后缀最小值即可。

还要注意排序时若 x-y 相同要再按 x 为第二关键字降序排序，这样才能保证包含了所有满足条件的点对。其他三个部分都是一样的，把条件和最大化的东西理清出，重复上述过程就完成了建图，直接跑 Kruskal 即可。

AC Code:

十年 OI 一场空，不开 long long 见祖宗！

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N=2e5+10,inf=1e18;
struct Node{int _x,_y,x,y,id,d,s;}p[N];
struct Edge{int u,v,w;}e[N<<2];
bool operator<(Edge x,Edge y){return x.w<y.w;}
int n,cnt,a[N<<2];
bool cmp1(Node a,Node b){return a.d^b.d?a.d>b.d:a.x>b.x;}
bool cmp2(Node a,Node b){return a.d^b.d?a.d<b.d:a.x>b.x;}
bool cmp3(Node a,Node b){return a.s^b.s?a.s>b.s:a.y<b.y;}
bool cmp4(Node a,Node b){return a.s^b.s?a.s<b.s:a.y>b.y;}
pii t[N<<1];
void init(){
    for(int i=1;i<=2*n;i++)
        t[i]={inf,0ll};
}
void upd(int x,pii y){
    for(;x<=2*n;x+=x&-x)
        t[x]=min(t[x],y);
}
pii qry(int x){
    pii res={inf,0};
    for(;x;x-=x&-x)
        res=min(res,t[x]);
    return res;
}
int dis(int x,int y){return abs(p[x]._x-p[y]._x)+abs(p[x]._y-p[y]._y);}
void build(){
    init(),sort(p+1,p+n+1,cmp1);
    for(int i=1;i<=n;i++){
        pii t=qry(2*n-p[i].x+1);
        if(t.fi<inf)
            e[++cnt]={p[i].id,p[t.se].id,dis(i,t.se)};
        upd(2*n-p[i].x+1,{p[i].s,i});
    }
    init(),sort(p+1,p+n+1,cmp2);
    for(int i=1;i<=n;i++){
        pii t=qry(2*n-p[i].y+1);
        if(t.fi<inf)
            e[++cnt]={p[i].id,p[t.se].id,dis(i,t.se)};
        upd(2*n-p[i].y+1,{p[i].s,i});
    }
    init(),sort(p+1,p+n+1,cmp3);
    for(int i=1;i<=n;i++){
        pii t=qry(p[i].x);
        if(t.fi<inf)
            e[++cnt]={p[i].id,p[t.se].id,dis(i,t.se)};
        upd(p[i].x,{p[i].d,i});
    }
    init(),sort(p+1,p+n+1,cmp4);
    for(int i=1;i<=n;i++){
        pii t=qry(2*n-p[i].y+1);
        if(t.fi<inf)
            e[++cnt]={p[i].id,p[t.se].id,dis(i,t.se)};
        upd(2*n-p[i].y+1,{p[i].d,i});
    }
}
int ans,f[N];
vector<int>G;
int find(int x){return(x==f[x]?x:f[x]=find(f[x]));}
void Kruskal(){
    for(int i=1;i<=n;i++)f[i]=i;
    sort(e+1,e+cnt+1);
    for(int i=1,U,V;i<=cnt;i++){
        U=find(e[i].u),V=find(e[i].v);
        if(U==V)continue;
        ans+=e[i].w,f[U]=V;
        G.push_back(i);
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i].x>>p[i].y,p[i].id=i,
        p[i].d=p[i].y-p[i].x,p[i].s=p[i].x+p[i].y,
        a[i]=p[i].x,a[i+n]=p[i].y;
    sort(a+1,a+2*n+1);
    for(int i=1;i<=n;i++)
        p[i]._x=p[i].x,p[i]._y=p[i].y,
        p[i].x=lower_bound(a+1,a+2*n+1,p[i].x)-a,
        p[i].y=lower_bound(a+1,a+2*n+1,p[i].y)-a;
    build();
    Kruskal();
    cout<<ans<<'\n';
    for(int i:G)cout<<e[i].u<<' '<<e[i].v<<'\n';
    return 0;
}

完结撒花！！！