This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/graph/manhattan_mst.hpp"
$N$ 個の点 $(x_i,y_i)$ が与えられた場合に,点の間の距離をマンハッタン距離 $\vert x _ i - x _ j\vert + \vert y _ i - y _ j\vert$ としたの重み付き完全無向グラフの最小全域木を $O(N\log N)$ 時間で計算する.
#ifndef SUISEN_MANHATTAN_MST #define SUISEN_MANHATTAN_MST #include <limits> #include <numeric> #include <tuple> #include "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp" #include "library/graph/kruscal.hpp" namespace suisen { namespace internal::manhattan_mst { template <typename T> std::pair<T, int> op(std::pair<T, int> x, std::pair<T, int> y) { return std::max(x, y); }; template <typename T> std::pair<T, int> e() { return { std::numeric_limits<T>::min(), -1 }; }; template <typename T> using PrefixMaxQuery = FenwickTreePrefix<std::pair<T, int>, op<T>, e<T>>; } // namespace internal::manhattan_mst template <typename WeightType, typename T> KruscalMinimumSpanningTree<WeightType> manhattan_mst(std::vector<std::pair<T, T>> points) { using namespace internal::manhattan_mst; const int n = points.size(); std::vector<int> p(n); std::iota(p.begin(), p.end(), 0); auto make_edges = [&](KruscalMinimumSpanningTree<WeightType> &mst) { std::sort( p.begin(), p.end(), [&points](int i, int j) { const auto &[xi, yi] = points[i]; const auto &[xj, yj] = points[j]; return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj; } ); std::vector<T> comp_x(n); for (int i = 0; i < n; ++i) comp_x[i] = points[i].first; std::sort(comp_x.begin(), comp_x.end()); comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end()); const int m = comp_x.size(); auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); }; PrefixMaxQuery<T> pmq(m); for (int i : p) { const auto& [x, y] = points[i]; const int cx = compress(x); if (const auto p = pmq.prefix_query(cx + 1); p != e<T>()) { const auto& [v, j] = p; mst.add_edge(i, j, x + y - v); } pmq.apply(cx, { x + y, i }); } }; KruscalMinimumSpanningTree<WeightType> mst(n); for (int x_rev = 0; x_rev < 2; ++x_rev) { for (int y_rev = 0; y_rev < 2; ++y_rev) { for (int xy_rev = 0; xy_rev < 2; ++xy_rev) { make_edges(mst); for (auto& [x, y] : points) std::swap(x, y); } for (auto& [x, _] : points) x = -x; } for (auto& [_, y] : points) y = -y; } assert(mst.build()); return mst; } } // namespace suisen #endif // SUISEN_MANHATTAN_MST
#line 1 "library/graph/manhattan_mst.hpp" #include <limits> #include <numeric> #include <tuple> #line 1 "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp" #include <vector> namespace suisen { template <typename T, T(*op)(T, T), T(*e)()> struct FenwickTreePrefix { FenwickTreePrefix() : FenwickTreePrefix(0) {} explicit FenwickTreePrefix(int n) : _n(n), _dat(_n + 1, e()) {} FenwickTreePrefix(const std::vector<T> &dat) : _n(dat.size()), _dat(_n + 1, e()) { for (int i = _n; i > 0; --i) { _dat[i] = op(_dat[i], dat[i - 1]); if (int p = i + (-i & i); p <= _n) _dat[p] = op(_dat[p], _dat[i]); } } void apply(int i, const T& val) { for (++i; i <= _n; i += -i & i) _dat[i] = op(_dat[i], val); } T prefix_query(int r) const { T res = e(); for (; r; r -= -r & r) res = op(res, _dat[r]); return res; } private: int _n; std::vector<T> _dat; }; } // namespace suisen #line 1 "library/graph/kruscal.hpp" #include <atcoder/dsu> namespace suisen { namespace internal::kruscal { // CostType: a type represents weights of edges i.e. (unsigned) int, (unsigned) long long, ... template <typename CostType, typename ComparatorType> struct KruscalMST { using cost_type = CostType; using edge_type = std::tuple<int, int, cost_type>; using comparator_type = ComparatorType; KruscalMST() : KruscalMST(0) {} explicit KruscalMST(const int n) : _n(n) {} void add_edge(const int u, const int v, const cost_type& cost) { _built = false; _edges.emplace_back(u, v, cost); } void add_edge(const edge_type& e) { _built = false; _edges.push_back(e); } /** * constructs the MST in O(ElogE) time using Kruskal's algprithm (E is the number of edges). * return: whether there exists MST or not (i.e. the graph is connected or not) */ bool build() { _built = true; _weight_sum = 0; if (_n == 0) return true; atcoder::dsu uf(_n); std::sort(_edges.begin(), _edges.end(), [this](const auto& e1, const auto& e2) { return _comp(std::get<2>(e1), std::get<2>(e2)); }); for (auto& [u, v, w] : _edges) { if (uf.same(u, v)) { u = v = _n; } else { uf.merge(u, v); _weight_sum += w; } } _edges.erase(std::remove_if(_edges.begin(), _edges.end(), [this](auto& e) { return std::get<0>(e) == _n; }), _edges.end()); return int(_edges.size()) == _n - 1; } /** * ! This must not be called before calling `solve()`. * return: * 1. connected: sum of weights of edges in the minimum spanning tree * 2. otherwise: sum of weights of edges in the minimum spanning forest */ cost_type get_weight() const { assert(_built); return _weight_sum; } /** * ! This must not be called before calling `solve()`. * return: * 1. connected: edges in the minimum spanning tree * 2. otherwise: edges in the minimum spanning forest * It is guaranteed that edges[i] <= edges[j] iff i <= j. */ const std::vector<edge_type>& get_mst() const { assert(_built); return _edges; } private: int _n; cost_type _weight_sum; std::vector<edge_type> _edges; bool _built = false; comparator_type _comp{}; }; } // namespace internal::kruscal template <typename CostType> using KruscalMinimumSpanningTree = internal::kruscal::KruscalMST<CostType, std::less<CostType>>; template <typename CostType> using KruscalMaximumSpanningTree = internal::kruscal::KruscalMST<CostType, std::greater<CostType>>; } // namespace suisen #line 11 "library/graph/manhattan_mst.hpp" namespace suisen { namespace internal::manhattan_mst { template <typename T> std::pair<T, int> op(std::pair<T, int> x, std::pair<T, int> y) { return std::max(x, y); }; template <typename T> std::pair<T, int> e() { return { std::numeric_limits<T>::min(), -1 }; }; template <typename T> using PrefixMaxQuery = FenwickTreePrefix<std::pair<T, int>, op<T>, e<T>>; } // namespace internal::manhattan_mst template <typename WeightType, typename T> KruscalMinimumSpanningTree<WeightType> manhattan_mst(std::vector<std::pair<T, T>> points) { using namespace internal::manhattan_mst; const int n = points.size(); std::vector<int> p(n); std::iota(p.begin(), p.end(), 0); auto make_edges = [&](KruscalMinimumSpanningTree<WeightType> &mst) { std::sort( p.begin(), p.end(), [&points](int i, int j) { const auto &[xi, yi] = points[i]; const auto &[xj, yj] = points[j]; return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj; } ); std::vector<T> comp_x(n); for (int i = 0; i < n; ++i) comp_x[i] = points[i].first; std::sort(comp_x.begin(), comp_x.end()); comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end()); const int m = comp_x.size(); auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); }; PrefixMaxQuery<T> pmq(m); for (int i : p) { const auto& [x, y] = points[i]; const int cx = compress(x); if (const auto p = pmq.prefix_query(cx + 1); p != e<T>()) { const auto& [v, j] = p; mst.add_edge(i, j, x + y - v); } pmq.apply(cx, { x + y, i }); } }; KruscalMinimumSpanningTree<WeightType> mst(n); for (int x_rev = 0; x_rev < 2; ++x_rev) { for (int y_rev = 0; y_rev < 2; ++y_rev) { for (int xy_rev = 0; xy_rev < 2; ++xy_rev) { make_edges(mst); for (auto& [x, y] : points) std::swap(x, y); } for (auto& [x, _] : points) x = -x; } for (auto& [_, y] : points) y = -y; } assert(mst.build()); return mst; } } // namespace suisen