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

• View this file on GitHub
• Last update: 2023-11-04 18:06:00+09:00
• Include: #include "graph/range-edge-graph.hpp"

Depends on

• グラフ構造体 (graph/graph_template.hpp)

Code

#pragma once

#include "graph_template.hpp"

template <typename Cost = int> class RangeEdgeGraph {
  public:
    explicit RangeEdgeGraph(int n, int m) : N(n), M(0), G(3 * N + m) {
        for(int i = 1; i < N; i++) {
            G.add_directed_edge(i, (i << 1 | 0), 0);
            G.add_directed_edge(i, (i << 1 | 1), 0);
            G.add_directed_edge((i << 1 | 0) + N * 2, i + N * 2, 0);
            G.add_directed_edge((i << 1 | 1) + N * 2, i + N * 2, 0);
        }
    }
    void add_edge(int from_l, int from_r, int to_l, int to_r, Cost cost) {
        assert(0 <= from_l and from_l < from_r and from_r <= N);
        assert(0 <= to_l and to_l < to_r and to_r <= N);
        assert(3 * N + M < (int)G.size());
        int id = 3 * N + M;
        M++;
        from_l += N;
        from_r += N;
        while(from_l < from_r) {
            if(from_l & 1) G.add_directed_edge(from_l + 2*N, id, 0), from_l++;
            if(from_r & 1) from_r--, G.add_directed_edge(from_r + 2*N, id, 0);
            from_l <<= 1;
            from_r <<= 1;
        }
        to_l += N;
        to_r += N;
        while(to_l < to_r) {
            if(to_l & 1) G.add_directed_edge(id, to_l, cost), to_l++;
            if(to_r & 1) to_r--, G.add_directed_edge(id, to_r, cost);
            to_l <<= 1;
            to_r <<= 1;
        }
    }
    operator Graph<Cost>() const { return G; }

  private:
    int N, M;
    Graph<Cost> G;
};

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

#line 2 "graph/graph_template.hpp"

#include <cassert>
#include <vector>

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;
#line 4 "graph/range-edge-graph.hpp"

template <typename Cost = int> class RangeEdgeGraph {
  public:
    explicit RangeEdgeGraph(int n, int m) : N(n), M(0), G(3 * N + m) {
        for(int i = 1; i < N; i++) {
            G.add_directed_edge(i, (i << 1 | 0), 0);
            G.add_directed_edge(i, (i << 1 | 1), 0);
            G.add_directed_edge((i << 1 | 0) + N * 2, i + N * 2, 0);
            G.add_directed_edge((i << 1 | 1) + N * 2, i + N * 2, 0);
        }
    }
    void add_edge(int from_l, int from_r, int to_l, int to_r, Cost cost) {
        assert(0 <= from_l and from_l < from_r and from_r <= N);
        assert(0 <= to_l and to_l < to_r and to_r <= N);
        assert(3 * N + M < (int)G.size());
        int id = 3 * N + M;
        M++;
        from_l += N;
        from_r += N;
        while(from_l < from_r) {
            if(from_l & 1) G.add_directed_edge(from_l + 2*N, id, 0), from_l++;
            if(from_r & 1) from_r--, G.add_directed_edge(from_r + 2*N, id, 0);
            from_l <<= 1;
            from_r <<= 1;
        }
        to_l += N;
        to_r += N;
        while(to_l < to_r) {
            if(to_l & 1) G.add_directed_edge(id, to_l, cost), to_l++;
            if(to_r & 1) to_r--, G.add_directed_edge(id, to_r, cost);
            to_l <<= 1;
            to_r <<= 1;
        }
    }
    operator Graph<Cost>() const { return G; }

  private:
    int N, M;
    Graph<Cost> G;
};

Back to top page