简要题意

有 \(n\) 个点，每个点有两个属性 \((x,y)\)。连无向边 \((A,B)\) 的代价是 \(\min(|A_x-B_x|,|A_y,B_y|)\)。

你需要连接这 \(n\) 个点，使得它们任意两点之间连通，求最小代价。

\(2 \leq n \leq 10^5\)

思路

代价带 \(\min\) 不好处理，我们考虑将代价的 \(\min\) 拆开，改成连两条边，一条边代价是 \(|A_x-B_x|\)，一条边代价是 \(|A_y-B_y|\)。然后答案是两个方案的并的最小生成树。

然后我们就可以考虑如何求出只连 \(|A_x-B_x|\) 的方案？我们可以按 \(x\) 排序，然后依次连出一条链。这样最忧。

对于 \(y\)，我们也可以按 \(y\) 排序，然后依次连出一条链。

最后把这两条连组合起来，形成一个无向图，求出最小边权和即可。

时间复杂度 \(O(n\log n)\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct edge{
    int u,v,w,id;
} g[1000005],a[1000005];
int n,tot;

int fa[1000005];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].u>>a[i].v;
        a[i].id=i;
    }
    sort(a+1,a+n+1,[](edge x,edge y){
        return x.u<y.u;
    });
    for(int i=1;i<n;i++){
        g[++tot]={a[i].id,a[i+1].id,(a[i+1].u-a[i].u)};
    }
    sort(a+1,a+n+1,[](edge x,edge y){
        return x.v<y.v;
    });
    for(int i=1;i<n;i++){
        g[++tot]={a[i].id,a[i+1].id,(a[i+1].v-a[i].v)};
    }
    sort(g+1,g+tot+1,[](edge x,edge y){
        return x.w<y.w;
    });
    int ans=0,cnt=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=tot;i++){
        int u=g[i].u,v=g[i].v,w=g[i].w;
        assert(g[i].id==0);
        if(find(u)==find(v)){
            continue;
        }
        ans+=w;
        fa[find(u)]=find(v);
        cnt++;
        if(cnt>=(n-1)) break;
    }
    cout<<ans;
    return 0;
}