Manhattan MST
(DataStructure/manhattanmst.hpp)

• View this file on GitHub
• Last update: 2023-01-17 01:31:58+09:00
• Include: #include "DataStructure/manhattanmst.hpp"

Depends on

• Union Find (DataStructure/unionfind.hpp)

Verified with

• Verify/LC_manhattanmst.test.cpp

Code

#pragma once
#include "DataStructure/unionfind.hpp"

template<typename T>pair<T,vector<pair<int,int>>> ManhattanMST(vector<T>& X,vector<T>& Y){
    using Q=pair<T,pair<int,int>>;
    int n=X.size();
    vector<int> ord(n);
    iota(ALL(ord),0);
    vector<Q> cand;
    rep(_,0,2){
        rep(__,0,2){
            sort(ALL(ord),[&](int i,int j){return X[i]+Y[i]<X[j]+Y[j];});
            map<T,int> sweep;
            for(auto& i:ord){
                for(auto it=sweep.lower_bound(-Y[i]);it!=sweep.end();it=sweep.erase(it)){
                    int j=it->second;
                    if(X[i]-X[j]<Y[i]-Y[j])break;
                    cand.push_back({abs(X[i]-X[j])+abs(Y[i]-Y[j]),{i,j}});
                }
                sweep[-Y[i]]=i;
            }
            swap(X,Y);
        }
        for(auto& x:X)x=-x;
    }
    sort(ALL(cand));
    UnionFind uni(n);
    T ret=0;
    vector<pair<int,int>> es;
    for(auto& [cost,uv]:cand){
        auto [u,v]=uv;
        if(uni.unite(u,v)){
            ret+=cost;
            es.push_back(uv);
        }
    }
    return {ret,es};
}

/**
 * @brief Manhattan MST
*/

#line 2 "DataStructure/unionfind.hpp"

struct UnionFind{
    vector<int> par; int n;
    UnionFind(){}
    UnionFind(int _n):par(_n,-1),n(_n){}
    int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
    bool same(int x,int y){return root(x)==root(y);}
    int size(int x){return -par[root(x)];}
    bool unite(int x,int y){
        x=root(x),y=root(y); if(x==y)return false;
        if(size(x)>size(y))swap(x,y);
        par[y]+=par[x]; par[x]=y; n--; return true;
    }
};

/**
 * @brief Union Find
 */
#line 3 "DataStructure/manhattanmst.hpp"

template<typename T>pair<T,vector<pair<int,int>>> ManhattanMST(vector<T>& X,vector<T>& Y){
    using Q=pair<T,pair<int,int>>;
    int n=X.size();
    vector<int> ord(n);
    iota(ALL(ord),0);
    vector<Q> cand;
    rep(_,0,2){
        rep(__,0,2){
            sort(ALL(ord),[&](int i,int j){return X[i]+Y[i]<X[j]+Y[j];});
            map<T,int> sweep;
            for(auto& i:ord){
                for(auto it=sweep.lower_bound(-Y[i]);it!=sweep.end();it=sweep.erase(it)){
                    int j=it->second;
                    if(X[i]-X[j]<Y[i]-Y[j])break;
                    cand.push_back({abs(X[i]-X[j])+abs(Y[i]-Y[j]),{i,j}});
                }
                sweep[-Y[i]]=i;
            }
            swap(X,Y);
        }
        for(auto& x:X)x=-x;
    }
    sort(ALL(cand));
    UnionFind uni(n);
    T ret=0;
    vector<pair<int,int>> es;
    for(auto& [cost,uv]:cand){
        auto [u,v]=uv;
        if(uni.unite(u,v)){
            ret+=cost;
            es.push_back(uv);
        }
    }
    return {ret,es};
}

/**
 * @brief Manhattan MST
*/

Back to top page