range edge graph (区間に辺を貼るテク)
(src/graph/range-edge-graph.hpp)

• View this file on GitHub
• Last update: 2022-12-14 06:57:55+09:00
• Include: #include "src/graph/range-edge-graph.hpp"

概要

$l_1\ \le\ u\ <\ r_1, l_2\ \le\ v\ <\ r_2$ について、 $u$ から $v$ に有向辺を貼るという操作を行うことができる。

機能

• range_edge_graph<cost_type> reg(int n)
  • コンストラクタ
  • cost_type: 辺の重みの型（テンプレート引数）
    • int、long、long longのいずれかでの使用を想定しています。
  • n: 頂点数（int）
  • 計算量 : $O(N)$
• void add_edge(int ul, int ur, int vl, int vr, cost_type w)
  • 区間 $[ \text{ul},\ \text{ur})$ から区間 $[ \text{vl},\ \text{vr})$ にコスト $\text{w}$ の有向辺を貼る
  • $0\ \le\ \text{ul},\ \text{vl}\ <\ n$
  • $\text{ul}\ \le\ \text{ur}\ \le\ n$
  • $\text{vl}\ \le\ \text{vr}\ \le\ n$
  • 計算量: $O(\log n)$
• std::vector<cost_type> dijkstra(int s, cost_type sup = std::numeric_limits<cost_type>::max()
  • 頂点sからの最短経路表を返す。
  • sup はデフォルトで値が設定されていますが、自分で指定することを強く推奨します。
  • $0\ \le\ s\ <\ n$
  • 返り値: 始点sから頂点iへの最短コストがres[i]に入る。要素数nのstd::vector<cost_type>
  • 計算量 : 辺の追加回数を $E$ として $O((n + E\log n)\log n)$

参考

tweet by @noshi91

区間に辺を貼るテクの実装例（Dijkstra法セット）と使用例

Verified with

• test/range-edge-graph1.test.cpp
• test/range-edge-graph2.test.cpp

Code

#pragma once

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class cost_type>
class range_edge_graph {
private:
    int n;
    std::vector<std::vector<std::pair<int, cost_type>>> G;

    void add_edge(int u, int v, cost_type cost) {
        if (u >= 3 * n) {
            u -= 2 * n;
        }
        G[u].emplace_back(v, cost);
    }

public:
    range_edge_graph(int n) : n(n), G(3 * n) {
        for (int i = 1 ; i < n ; i++) {
            int child_l = ((i << 1) | 0), child_r = ((i << 1 | 1));
            add_edge(i, child_l, 0);
            add_edge(i, child_r, 0);
            add_edge(child_l + 2 * n, i + 2 * n, 0);
            add_edge(child_r + 2 * n, i + 2 * n, 0);
        }
    }

    void add_edge(int ul, int ur, int vl, int vr, cost_type cost) {
        int id = G.size();
        for (int l = ul + n, r = ur + n ; l < r ; l >>= 1, r >>= 1) {
            if (l & 1) {
                add_edge(l + 2 * n, id, 0);
                l++;
            }
            if (r & 1) {
                r--;
                add_edge(r + 2 * n, id, 0);
            }
        }
        std::vector<std::pair<int, cost_type>> node;
        for (int l = vl + n, r = vr + n ; l < r ; l >>= 1, r >>= 1) {
            if (l & 1) {
                node.emplace_back(l, cost);
                l++;
            }
            if (r & 1) {
                r--;
                node.emplace_back(r, cost);
            }
        }
        G.push_back(node);
    }

    std::vector<cost_type> dijkstra(int s, cost_type sup = std::numeric_limits<cost_type>::max()) {
        std::priority_queue<
            std::pair<cost_type, int>, 
            std::vector<std::pair<cost_type, int>>, 
            std::greater<std::pair<cost_type, int>>
                > que;
        que.emplace((cost_type)0, s + n);
        std::vector<cost_type> dist(G.size(), sup);
        dist[s + n] = (cost_type)0;
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (d > dist[v]) {
                continue;
            }
            for (auto [x, cost] : G[v]) {
                if (dist[x] > d + cost) {
                    dist[x] = d + cost;
                    que.emplace(d + cost, x);
                }
            }
        }
        return std::vector<cost_type>(dist.begin() + n, dist.begin() + 2 * n);
    }

};

} // namespace zawa

#line 2 "src/graph/range-edge-graph.hpp"

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class cost_type>
class range_edge_graph {
private:
    int n;
    std::vector<std::vector<std::pair<int, cost_type>>> G;

    void add_edge(int u, int v, cost_type cost) {
        if (u >= 3 * n) {
            u -= 2 * n;
        }
        G[u].emplace_back(v, cost);
    }

public:
    range_edge_graph(int n) : n(n), G(3 * n) {
        for (int i = 1 ; i < n ; i++) {
            int child_l = ((i << 1) | 0), child_r = ((i << 1 | 1));
            add_edge(i, child_l, 0);
            add_edge(i, child_r, 0);
            add_edge(child_l + 2 * n, i + 2 * n, 0);
            add_edge(child_r + 2 * n, i + 2 * n, 0);
        }
    }

    void add_edge(int ul, int ur, int vl, int vr, cost_type cost) {
        int id = G.size();
        for (int l = ul + n, r = ur + n ; l < r ; l >>= 1, r >>= 1) {
            if (l & 1) {
                add_edge(l + 2 * n, id, 0);
                l++;
            }
            if (r & 1) {
                r--;
                add_edge(r + 2 * n, id, 0);
            }
        }
        std::vector<std::pair<int, cost_type>> node;
        for (int l = vl + n, r = vr + n ; l < r ; l >>= 1, r >>= 1) {
            if (l & 1) {
                node.emplace_back(l, cost);
                l++;
            }
            if (r & 1) {
                r--;
                node.emplace_back(r, cost);
            }
        }
        G.push_back(node);
    }

    std::vector<cost_type> dijkstra(int s, cost_type sup = std::numeric_limits<cost_type>::max()) {
        std::priority_queue<
            std::pair<cost_type, int>, 
            std::vector<std::pair<cost_type, int>>, 
            std::greater<std::pair<cost_type, int>>
                > que;
        que.emplace((cost_type)0, s + n);
        std::vector<cost_type> dist(G.size(), sup);
        dist[s + n] = (cost_type)0;
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (d > dist[v]) {
                continue;
            }
            for (auto [x, cost] : G[v]) {
                if (dist[x] > d + cost) {
                    dist[x] = d + cost;
                    que.emplace(d + cost, x);
                }
            }
        }
        return std::vector<cost_type>(dist.begin() + n, dist.begin() + 2 * n);
    }

};

} // namespace zawa

Back to top page