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

FFTotoro · 2025-04-18 15:05:32 · 题解

本文在结论的证明上参考了：曼哈顿距离最小生成树 - 博客园，在此表示对作者的感谢。

下文中对于平面中的两个点 A 和 B，记 |AB| 表示 A 和 B 的曼哈顿距离，即 |AB|=|x_A-x_B|+|y_A-y_B|。

对于完全图最小生成树一类题，一种直接的想法是使用蓝莓算法解决。但是我们将会在这里介绍一种直接使用 Kruskal 的解法。

观察到本题边数很多，而 Kruskal 是基于边的贪心，所以只有一条道路——去掉必然不会被选择的边，只保留少量的边求解。

先给出结论：对于每个点 (x,y)，如下图将平面划分为 8 个 45\degree 的区域（(x,y) 为四条分割线的交点，其中两条分割线分别与 x 轴与 y 轴平行），将该点与每个区域中离它最近的任意一个点连边即可。下证为什么这样的连边方式是最优的。

证明：

设 (x,y) 为原点 O(0,0)，在上面的 R_1 中考虑两个点 A(x_1,y_1),B(x_2,y_2)（其他区域同理；由于在区域 R_1 中所以满足 0\le x_1\le y_1 和 0\le x_2\le y_2），不妨认为 |OA|\le |OB|。根据最小生成树的性质，对于原图的一个三元环，其中的最长边一定不会被选入最小生成树，故只需证：|AB|\le |OB|，即 OB 可以被忽略。

分类讨论 x_1,x_2,y_1,y_2 四者的关系：

综上，该结论成立。

现在的问题在于，如何找出这些边。可以观察到一个事情，事实上只需要考虑区域 R_1,R_2,R_3,R_4 中的点进行连边（因为每条边必然有一个点 x 坐标较小，相当于将其与 x 坐标较大的连边），常数能够除以 2。

考虑如何快速找到单个区域中离一个点 A(x,y) 最近的点：以区域 R_1 为例，对于一个点 B(x',y')，由于在区域 R_1 所以满足 x'\ge x\land y'-x'\ge y-x，又因为 |AB|=x'-x+y'-y，所以需要最小化 x'+y'。

对于这一类二维偏序问题，考虑按其中一维排序，在数据结构上维护另一维。观察到需要维护的是最值，又由于需要求值的下标范围是一个后缀，所以直接上树状数组维护。

求解除了 R_1 以外的其他区域很简单，只需要合理地组合使用下面的操作进行坐标变换即可：

交换 x 坐标和 y 坐标，即将一个点关于直线 x=y 轴对称；
将 x 坐标取相反数，即将一个点关于直线 x=0 轴对称。

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

参考代码（GNU C++ 17）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(){
        a.resize(200000),s.resize(200000,1);
        iota(a.begin(),a.end(),0);
      }
      dsu(int n){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  }; // 并查集模板
  template<typename T,T(*op)(T,T),T(*e)()> class fenwick_tree{
    private:
      vector<T> t;
    public:
      fenwick_tree(){
        t.resize(200000,e());
      }
      fenwick_tree(int n){
        t.resize(n,e());
      }
      inline int lowbit(int x){
        return x&-x;
      }
      inline void add(int p,T d){
        t[p]=op(t[p],d),p++;
        while((p-=lowbit(p))>0)
          t[p-1]=op(t[p-1],d);
      }
      inline T suf_sum(int p){
        T s=t[p++];
        while((p+=lowbit(p))<=t.size())
          s=op(s,t[p-1]);
        return s;
      }
  }; // 维护后缀信息的树状数组模板
  inline pii mn(pii x,pii y){return x<y?x:y;}
  inline pii id(){return make_pair(2e9,-1);}
  inline pair<ll,vector<pii> > mst(vector<tpi> e,int n=1){
    vector<pii> e2;
    for(auto [u,v,w]:e)n=max({n,u+1,v+1});
    sort(e.begin(),e.end(),[](tpi x,tpi y){
      return get<2>(x)<get<2>(y);
    });
    dsu<int> d(n); ll r=0;
    for(auto [u,v,w]:e)
      if(!d.same(u,v))d.merge(u,v),e2.emplace_back(u,v),r+=w;
    return make_pair(r,e2);
  } // Kruskal 求解最小生成树
  inline pair<ll,vector<pii> > manhattan_mst(vector<pii> p){
    vector<tpi> e;
    for(int r1=0;r1<2;r1++){
      for(auto &[x,y]:p)x=-x;
      for(int r2=0;r2<2;r2++){
        vector<int> a(p.size()),b;
        for(auto &[x,y]:p)
          swap(x,y),b.emplace_back(x);
        sort(b.begin(),b.end());
        b.erase(unique(b.begin(),b.end()),b.end());
        auto get=[&](int x){
          return lower_bound(b.begin(),b.end(),x)-b.begin();
        }; // 对坐标离散化
        iota(a.begin(),a.end(),0);
        sort(a.begin(),a.end(),[&](int x,int y){
          int dx=p[x].second-p[x].first,dy=p[y].second-p[y].first;
          return dx==dy?p[x].first>p[y].first:dx>dy;
        }); // 对第一维排序
        fenwick_tree<pii,mn,id> t(b.size());
        for(int i=0;i<p.size();i++){
          auto [x,y]=p[a[i]];
          int w=get(x);
          auto [s,j]=t.suf_sum(w);
          if(~j)e.emplace_back(a[i],a[j],s-x-y);
          t.add(w,make_pair(x+y,i));
        } // 树状数组求距离最短点
      }
    }
    return mst(e);
  }
}
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<pii> a(n);
  for(auto &[x,y]:a)cin>>x>>y;
  auto [w,e]=IAOI_lib::manhattan_mst(a);
  cout<<w<<endl;
  for(auto [u,v]:e)cout<<u+1<<' '<<v+1<<'\n';
  return 0;
}

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

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