manhattan_mst.hpp¶
#include "noya/manhattan_mst.hpp"
#ifndef NOYA_MANHATTAN_MST_HPP
#define NOYA_MANHATTAN_MST_HPP 1
#include "noya/minimum_spanning_tree.hpp"
#include <algorithm>
#include <map>
#include <numeric>
#include <tuple>
#include <vector>
namespace noya {
/// @brief Compute candidate edges for Manhattan MST in O(n log n).
/// @return Sorted edges as (weight, vertex_i, vertex_j).
template <typename T>
std::vector<std::tuple<T, int, int>> manhattan_edges(std::vector<T> xs,
std::vector<T> ys) {
const int n = xs.size();
std::vector<int> idx(n);
std::iota(idx.begin(), idx.end(), 0);
std::vector<std::tuple<T, int, int>> ret;
for (int s = 0; s < 2; s++) {
for (int t = 0; t < 2; t++) {
auto cmp = [&](int i, int j) { return xs[i] + ys[i] < xs[j] + ys[j]; };
std::sort(idx.begin(), idx.end(), cmp);
std::map<T, int> sweep;
for (int i : idx) {
for (auto it = sweep.lower_bound(-ys[i]); it != sweep.end();
it = sweep.erase(it)) {
int j = it->second;
if (xs[i] - xs[j] < ys[i] - ys[j])
break;
ret.emplace_back(std::abs(xs[i] - xs[j]) + std::abs(ys[i] - ys[j]), i,
j);
}
sweep[-ys[i]] = i;
}
std::swap(xs, ys);
}
for (auto &x : xs)
x = -x;
}
std::sort(ret.begin(), ret.end());
return ret;
}
template <typename PointType>
auto manhattan_edges(const std::vector<PointType> &points) {
assert(!points.empty());
using CoordType = std::decay_t<decltype(std::get<0>(points[0]))>;
std::vector<CoordType> xs, ys;
for (const auto &point : points) {
xs.push_back(std::get<0>(point));
ys.push_back(std::get<1>(point));
}
return manhattan_edges(xs, ys);
}
} // namespace noya
#endif // NOYA_MANHATTAN_MST_HPP
#include <algorithm>
#include <cassert>
#include <map>
#include <numeric>
#include <tuple>
#include <vector>
namespace atcoder {
// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
return _leader(a);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
int _leader(int a) {
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = _leader(parent_or_size[a]);
}
};
} // namespace atcoder
namespace noya {
/// @brief Kruskal's MST. Edges are (w, u, v). @return (cost, edge indices).
template <class T>
std::pair<int64_t, std::vector<int>>
minimum_spanning_tree(int N, const std::vector<T> &edges) {
int64_t ans = 0;
std::vector<int> idx;
atcoder::dsu f(N);
int m = int(edges.size());
std::vector<int> p(m);
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(),
[&](int i, int j) { return edges[i] < edges[j]; });
for (auto &i : p) {
auto &[w, u, v] = edges[i];
assert(0 <= u && u < N);
assert(0 <= v && v < N);
if (!f.same(u, v)) {
ans += w;
f.merge(u, v);
idx.push_back(i);
}
}
return make_pair(ans, idx);
}
/// @brief Kruskal's maximum spanning tree. Edges are (w, u, v). @return (cost, edge indices).
template <class T>
std::pair<int64_t, std::vector<int>>
maximum_spanning_tree(int N, const std::vector<T> &edges) {
int64_t ans = 0;
std::vector<int> idx;
atcoder::dsu f(N);
int m = int(edges.size());
std::vector<int> p(m);
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(),
[&](int i, int j) { return edges[i] > edges[j]; });
for (auto &i : p) {
auto &[w, u, v] = edges[i];
assert(0 <= u && u < N);
assert(0 <= v && v < N);
if (!f.same(u, v)) {
ans += w;
f.merge(u, v);
idx.push_back(i);
}
}
return make_pair(ans, idx);
}
/// @brief Prim's MST for dense graphs. Edges are (w, u, v). @return (cost, edge indices).
template <class T>
std::pair<int64_t, std::vector<int>> prim_dense(int N,
const std::vector<T> &edges) {
std::vector<std::vector<int>> id(N, std::vector<int>(N, -1));
const int M = int(edges.size());
for (int i = 0; i < M; i++) {
auto [w, u, v] = edges[i];
assert(0 <= u && u < N);
assert(0 <= v && v < N);
id[u][v] = id[v][u] = i;
}
std::vector<int> idx;
std::vector<int> vis(N, 0);
std::vector<int> dis(N, -1);
auto cmp = [&](int a, int b) -> int {
if (a == -1)
return b;
if (b == -1)
return a;
auto [w1, u1, v1] = edges[a];
auto [w2, u2, v2] = edges[b];
return w1 < w2 ? a : b;
};
int64_t ans = 0;
int k = 0;
for (int t = 1; t < N; t++) {
vis[k] = 1;
int nx = -1;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
dis[i] = cmp(dis[i], id[k][i]);
nx = cmp(nx, dis[i]);
}
}
if (nx == -1)
break;
idx.push_back(nx);
{
auto [w, u, v] = edges[nx];
ans += w;
if (vis[u]) {
k = v;
} else {
k = u;
}
}
}
return make_pair(ans, idx);
}
} // namespace noya
namespace noya {
/// @brief Compute candidate edges for Manhattan MST in O(n log n).
/// @return Sorted edges as (weight, vertex_i, vertex_j).
template <typename T>
std::vector<std::tuple<T, int, int>> manhattan_edges(std::vector<T> xs,
std::vector<T> ys) {
const int n = xs.size();
std::vector<int> idx(n);
std::iota(idx.begin(), idx.end(), 0);
std::vector<std::tuple<T, int, int>> ret;
for (int s = 0; s < 2; s++) {
for (int t = 0; t < 2; t++) {
auto cmp = [&](int i, int j) { return xs[i] + ys[i] < xs[j] + ys[j]; };
std::sort(idx.begin(), idx.end(), cmp);
std::map<T, int> sweep;
for (int i : idx) {
for (auto it = sweep.lower_bound(-ys[i]); it != sweep.end();
it = sweep.erase(it)) {
int j = it->second;
if (xs[i] - xs[j] < ys[i] - ys[j])
break;
ret.emplace_back(std::abs(xs[i] - xs[j]) + std::abs(ys[i] - ys[j]), i,
j);
}
sweep[-ys[i]] = i;
}
std::swap(xs, ys);
}
for (auto &x : xs)
x = -x;
}
std::sort(ret.begin(), ret.end());
return ret;
}
template <typename PointType>
auto manhattan_edges(const std::vector<PointType> &points) {
assert(!points.empty());
using CoordType = std::decay_t<decltype(std::get<0>(points[0]))>;
std::vector<CoordType> xs, ys;
for (const auto &point : points) {
xs.push_back(std::get<0>(point));
ys.push_back(std::get<1>(point));
}
return manhattan_edges(xs, ys);
}
} // namespace noya