目的 木(N頂点N-1辺であり、各頂点に必ずアクセスできるグラフ)の直径を求める。 直径とはグラフの最遠距離である。 関数 build( ): 木の直径を返す。path には直径を構成する辺が格納される。 コード template< typename T = int > struct TreeDiameter : G…

要約 ・コンテスト期間中に問題追加された場合は、contest.acc.jsonを直接編集し、$ acc add --force コマンドを実施する。 背景 E869120氏主催の「競プロ典型90問」を、AtCoderのジャッジを利用して挑戦中。 qiita.com atcoder.jp 普段自分はatcoder-cliとo…

目的 負辺のないグラフで単一始点全点間最短路を求めるアルゴリズム. 各地点でもっとも近い頂点から距離が確定していく. 距離順でソートされたヒープを用いると, 効率よく距離を確定していくことができる. オーダー O(ElogV) 条件 dijkstra(g, s): 重み付き…

説明 グラフを扱う際のテンプレート。 コード template <typename T = int> struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { retur</typename>…

目的 二次元格子状領域において、幅優先探索を行う。 また、要素xと要素yそれぞれが属するグループを併合することが可能。 オーダー O(HW) 条件 grid_bfs(s, start, wall):= グリッド s 上にある文字 start からすべてのマスへの最短距離を求める。wall には…