cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/graph/manhattan_mst/manhattanmst.test.cpp
- View this file on GitHub
- Last update: 2022-06-14 00:04:46+09:00
- Problem: https://judge.yosupo.jp/problem/manhattanmst
Depends on
- Fenwick Tree Prefix
(library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp)
- Kruscal
(library/graph/kruscal.hpp)
- Manhattan Mst
(library/graph/manhattan_mst.hpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst"
#include <iostream>
#include "library/graph/manhattan_mst.hpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::pair<int, int>> points(n);
for (auto &[x, y] : points) std::cin >> x >> y;
auto mst = suisen::manhattan_mst<long long>(points);
std::cout << mst.get_weight() << '\n';
for (auto [i, j, _] : mst.get_mst()) {
std::cout << i << ' ' << j << '\n';
}
return 0;
}#line 1 "test/src/graph/manhattan_mst/manhattanmst.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst"
#include <iostream>
#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
#line 6 "test/src/graph/manhattan_mst/manhattanmst.test.cpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::pair<int, int>> points(n);
for (auto &[x, y] : points) std::cin >> x >> y;
auto mst = suisen::manhattan_mst<long long>(points);
std::cout << mst.get_weight() << '\n';
for (auto [i, j, _] : mst.get_mst()) {
std::cout << i << ' ' << j << '\n';
}
return 0;
}