グラフテンプレート
(graph/template.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/template.hpp"

概要

グラフのテンプレート.

最短経路

• ダイクストラ法 : 単一始点最短路. 辺の重みが非負である必要がある. $O(E\log V)$
• ベルマンフォード法 : 単一始点最短路. 負閉路検出ができる. $O(EV)$
• ワーシャルフロイド法 : 全点間最短路. 負閉路検出ができる. $O(V^3)$
  • 辺の追加は$O(V^2)$

最小全域木

• クラスカル法 : UnionFindに依存. $O(E\log V)$

使用例

• Graph<int> g(V) : $V$頂点のグラフを定義.
• GINF<int> : グラフアルゴリズムで使うINF.
• g.input_edges(E, origin, need_cost) : 標準入力から無向辺を張る.
• g.input_arcs(E, origin, need_cost) : 標準入力から有向辺を張る.
  • origin : 辺を何originで受け取るか.
  • need_cost : コストを受け取るか.
    • true : U V cst
    • false : U V

Verified with

• test/aoj/2945.test.cpp
• test/aoj/GRL_1_A.test.cpp
• test/aoj/GRL_1_B.test.cpp
• test/aoj/GRL_1_C.test.cpp
• test/aoj/GRL_2_A.test.cpp
• test/aoj/GRL_4_B.test.cpp
• test/aoj/GRL_5_C.test.cpp
• test/aoj/GRL_5_D.test.cpp
• test/aoj/GRL_5_E.test.cpp
• test/aoj/GRL_7_A.test.cpp
• test/yosupo/vertexaddpathsum.test.cpp
• test/yosupo/vertexaddsubtreesum.test.cpp
• test/yukicoder/13.test.cpp
• test/yukicoder/20.test.cpp
• test/yukicoder/399.test.cpp

Code

/**
* @brief グラフテンプレート
* @docs docs/graph/template.md
*/

template <typename T>
struct Edge {
    int frm, to, idx;
    T cst;
    Edge() {}
    Edge(int f, int t, T c, int i = -1)
        : frm(f), to(t), idx(i), cst(c) {}
    operator int() const { return to; }
};

template <typename T>
constexpr T GINF = numeric_limits<T>::max() / 10;

template <typename T>
struct Graph {
    int V, E;
    vector<vector<Edge<T>>> mat;
    vector<vector<T>> wf;
    Graph() {}
    Graph(int v)
        : V(v), E(0), mat(v) {}
    inline void add_edge(int a, int b, T c = 1, int margin = 0) {
        a -= margin, b -= margin;
        mat[a].emplace_back(a, b, c, E++);
        mat[b].emplace_back(b, a, c, E++);
    }
    inline void add_arc(int a, int b, T c = 1, int margin = 0) {
        a -= margin, b -= margin;
        mat[a].emplace_back(a, b, c, E++);
    }
    inline void input_edges(int M, int margin = 0, bool need_cost = false) {
        for (int i = 0; i < M; ++i) {
            int a, b;
            T c(1);
            cin >> a >> b;
            if (need_cost) cin >> c;
            add_edge(a, b, c, margin);
        }
    }
    inline void input_arcs(int M, int margin = 0, bool need_cost = false) {
        for (int i = 0; i < M; ++i) {
            int a, b;
            T c(1);
            cin >> a >> b;
            if (need_cost) cin >> c;
            add_arc(a, b, c, margin);
        }
    }
};

#line 1 "graph/template.hpp"
/**
* @brief グラフテンプレート
* @docs docs/graph/template.md
*/

template <typename T>
struct Edge {
    int frm, to, idx;
    T cst;
    Edge() {}
    Edge(int f, int t, T c, int i = -1)
        : frm(f), to(t), idx(i), cst(c) {}
    operator int() const { return to; }
};

template <typename T>
constexpr T GINF = numeric_limits<T>::max() / 10;

template <typename T>
struct Graph {
    int V, E;
    vector<vector<Edge<T>>> mat;
    vector<vector<T>> wf;
    Graph() {}
    Graph(int v)
        : V(v), E(0), mat(v) {}
    inline void add_edge(int a, int b, T c = 1, int margin = 0) {
        a -= margin, b -= margin;
        mat[a].emplace_back(a, b, c, E++);
        mat[b].emplace_back(b, a, c, E++);
    }
    inline void add_arc(int a, int b, T c = 1, int margin = 0) {
        a -= margin, b -= margin;
        mat[a].emplace_back(a, b, c, E++);
    }
    inline void input_edges(int M, int margin = 0, bool need_cost = false) {
        for (int i = 0; i < M; ++i) {
            int a, b;
            T c(1);
            cin >> a >> b;
            if (need_cost) cin >> c;
            add_edge(a, b, c, margin);
        }
    }
    inline void input_arcs(int M, int margin = 0, bool need_cost = false) {
        for (int i = 0; i < M; ++i) {
            int a, b;
            T c(1);
            cin >> a >> b;
            if (need_cost) cin >> c;
            add_arc(a, b, c, margin);
        }
    }
};

Back to top page