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

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

下文中对于平面中的两个点

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$ 四者的关系：

$x_1>x_2\land y_1>y_2$ ：与 $|OA|\le |OB|$ 矛盾；

$x_1\le x_2\land y_1>y_2$ ：此时 $|AB|=x_2-x_1+y_1-y_2$ ，故 $|OB|-|AB|=x_2+y_2-(x_2-x_1+y_1-y_2)=x_1-y_1+2y_2$ 。如果 $|OB|<|AB|$ 则有 $y_1>x_1+2y_2$ ，故有 $|OA|=x_1+y_1>2x_1+2y_2$ ， $|OB|=x_2+y_2\le 2y_2<|OA|$ ，与 $|OA|\le |OB|$ 矛盾；

$x_1>x_2\land y_1\le y_2$ ：与 $x_1\le x_2\land y_1>y_2$ 的情况同理；

$x_1\le x_2\land y_1\le y_2$ ：此时 $|OA|+|AB|=|OB|$ ，始终满足 $|AB|\le |OB|$ 。

综上，该结论成立。

现在的问题在于，如何找出这些边。可以观察到一个事情，事实上只需要考虑区域

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）：

CPP

#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 曼哈顿距离最小生成树题解