概要 各辺に容量を持ち、始点と終点のあるグラフが与えられたとき、始点から終点までの最大フローを求める 最大フロー最小カット定理により、グラフの最小カットを求めることとも同値 グラフ中の辺 の容量が で、 から に だけフローが流れているとき、 に …

概要 記号列 とパターン が与えられたとき、 と一致する の部分列を探してその位置を返す 部分一致テーブル を事前に計算しておくことで、不一致となったときに次の探索を先頭からではなく途中までは既に部分一致したものとして一部スキップできる（場合があ…

概要 要素の更新がありうる数列について、区間和の計算が高速にできる 同様に更新ありの任意区間の区間和を高速に計算可能なSegment Treeと比較して空間計算量が半分程度 ただしSegment Treeのように最小値などの計算に使うといったような応用力はない Segme…

概要 組合せ数 の素数 による剰余を求める なので、それぞれの による剰余を求めればよい と帰納的に求めていくことで を求めることができる フェルマーの小定理より なので、両辺を で割ると が言える であることから残りは帰納的に求められる もしくは、 …

概要 要素の更新がありうる数列について、任意区間におけるあらかじめ定義した演算が高速にできる 最大値/最小値 一定値以上/以下の要素数 区間和 数列の各要素が葉となるような木構造をとる 木を構成する各nodeは自身の子node（葉の場合は自分自身）が表現…

概要 通常のキューは最初にPushしたアイテムを最初にPopする(FIFO) 優先度付きキューの場合、あらかじめ指定した任意の優先度に基づく順番でPopさせることができる 優先度はキューにPushされる任意のアイテム2つについて、その二者間に順序付けができるもの…

概要 グラフの連結成分について調べるために使用する Union()関数とFind()関数からなる 連結成分同士の結合をUnion()関数で実施する 同じ連結成分に属する頂点はFind()関数で同じ代表点が返ってくる Find()関数で経路圧縮すると、ならし計算量がAckerman関数…