Manhattan MST
(C++/graph/mst/manhattan.hpp)

• View this file on GitHub
• Last update: 2024-02-19 13:17:33+09:00
• Include: #include "C++/graph/mst/manhattan.hpp"
• Link: https://ei1333.github.io/library/graph/mst/manhattan-mst.hpp

Depends on

• Edge (C++/graph/edge.hpp)
• 最小全域木 (C++/graph/mst/MST.hpp)

Verified with

• test/manhattan.test.cpp

Code

#pragma once

#include <cassert>
#include <map>
#include <numeric>
#include "C++/graph/mst/MST.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 2 "C++/graph/mst/manhattan.hpp"

#include <cassert>
#include <map>
#include <numeric>
#line 2 "C++/graph/mst/MST.hpp"

#include <vector>
#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 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
 */

Back to top page