test/manhattan.test.cpp

View this file on GitHub
Last update: 2024-03-03 06:51:22+09:00
Problem: https://judge.yosupo.jp/problem/manhattanmst

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst"
#include <iostream>
#include "C++/graph/mst/kruskal.hpp"
#include "C++/graph/mst/manhattan.hpp"
int main() {
    int n;
    std::cin >> n;
    std::vector<int> x(n), y(n);
    for(int i = 0; i < n; ++i) {
        std::cin >> x[i] >> y[i];
    }
    const auto ans = kruskal(manhattan(x, y), n);
    std::cout << ans.cost << '\n';
    for(const auto &e: ans.tree) {
        std::cout << e.src << ' ' << e.to << '\n';
    }
}

#line 1 "test/manhattan.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst"
#include <iostream>
#line 2 "C++/graph/mst/kruskal.hpp"

#include <vector>
#line 2 "C++/graph/mst/MST.hpp"

#line 2 "C++/graph/edge.hpp"

struct edge {
    int src, to, id;
    long long cost;
    edge(){}
    edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
    operator int() const { return to; }
};

/**
 * @brief Edge
 */
#line 5 "C++/graph/mst/MST.hpp"
struct MST {
    std::vector<edge> tree;
    long long cost;
};

/**
 * @brief 最小全域木
 */
#line 2 "C++/ds/uf/UnionFind.hpp"

#include <cassert>

#line 5 "C++/ds/uf/UnionFind.hpp"
#include <algorithm>

struct UnionFind {
protected:
    std::vector<int> par;
public:
    UnionFind(const int n): par(n, -1){}
    int operator[](int i) {
        while(par[i] >= 0) {
            const int p = par[par[i]];
            if(p < 0) return par[i];
            i = par[i] = p;
        }
        return i;
    }
    bool unite(int x, int y) {
        x = (*this)[x], y = (*this)[y];
        if(x == y) return false;
        if(-par[x] < -par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y], par[y] = x;
        return true;
    }
    int size(const int x) {
        return -par[(*this)[x]];
    }
    int size() const { return par.size(); }
#if __cplusplus >= 202101L
    std::vector<std::vector<int>> groups() {
        const int n = std::ssize(par);
        std::vector<std::vector<int>> res(n);
        for(int i = 0; i < n; ++i) {
            res[(*this)[i]].emplace_back(i);
        }
        const auto it = std::ranges::remove_if(res, [&](const std::vector<int> &v){ return v.empty(); });
        res.erase(it.begin(), it.end());
        return res;
    }
#else
    std::vector<std::vector<int>> groups() {
        const int n = par.size();
        std::vector<std::vector<int>> res(n);
        for(int i = 0; i < n; ++i) {
            res[(*this)[i]].emplace_back(i);
        }
        res.erase(std::remove_if(res.begin(), res.end(), [&](const std::vector<int> &v){ return v.empty(); }), res.end());
        return res;
    }
#endif
};

inline bool is_bipartite(UnionFind uf) {
    assert(uf.size() % 2 == 0);
    const int n = uf.size() / 2;
    bool ok = true;
    for(int i = 0; i < n; ++i) {
        ok &= uf[i] != uf[i + n];
    }
    return ok;
}
/**
 * @brief UnionFind
 * @see https://github.com/maspypy/library/blob/main/ds/unionfind/unionfind.hpp
 */
#line 6 "C++/graph/mst/kruskal.hpp"
inline MST kruskal(std::vector<edge> edges, const int n) {
    std::sort(edges.begin(), edges.end(), [&](const edge &e, const edge &f){ return e.cost < f.cost; });
    UnionFind uf(n);
    std::vector<edge> e;
    long long res = 0;
    for(const auto &ed: edges) {
        if(uf.unite(ed.src, ed)) {
            e.emplace_back(ed);
            res += ed.cost;
        }
    }
    return {e, res};
}

/**
 * @brief Kruskal法
 */
#line 2 "C++/graph/mst/manhattan.hpp"

#line 4 "C++/graph/mst/manhattan.hpp"
#include <map>
#include <numeric>
#line 7 "C++/graph/mst/manhattan.hpp"
template <class T> inline std::vector<edge> manhattan(std::vector<T> x, std::vector<T> y) {
    assert(x.size() == y.size());
    std::vector<edge> res;
    std::vector<int> id(x.size());
    std::iota(id.begin(), id.end(), 0);
    for(int s = 0; s < 2; ++s) {
        for(int t = 0; t < 2; ++t) {
            std::sort(id.begin(), id.end(), [&](const int i, const int j){ return x[i] + y[i] < x[j] + y[j]; });
            std::map<T, int> idx;
            for(const auto i: id) {
                for(auto it = idx.lower_bound(-y[i]); it != idx.end(); it = idx.erase(it)) {
                    const int j = it -> second;
                    if(x[i] - x[j] < y[i] - y[j]) {
                        break;
                    }
                    res.emplace_back(i, j, -1, std::abs(x[i] - x[j]) + std::abs(y[i] - y[j]));
                }
                idx[-y[i]] = i;
            }
            x.swap(y);
        }
        for(size_t i = 0; i < x.size(); ++i) {
            x[i] *= -1;
        }
    }
    return res;
}

/**
 * @brief Manhattan MST
 * @see https://ei1333.github.io/library/graph/mst/manhattan-mst.hpp
 */
#line 5 "test/manhattan.test.cpp"
int main() {
    int n;
    std::cin >> n;
    std::vector<int> x(n), y(n);
    for(int i = 0; i < n; ++i) {
        std::cin >> x[i] >> y[i];
    }
    const auto ans = kruskal(manhattan(x, y), n);
    std::cout << ans.cost << '\n';
    for(const auto &e: ans.tree) {
        std::cout << e.src << ' ' << e.to << '\n';
    }
}