2020年3月20日数学最小公倍数,配列,結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, ...

2020年3月20日グラフ連結成分のサイズ,同じ連結成分か判定,幅優先探索,グラフ,深さ優先探索,連結成分,Union-Find

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

2020年3月20日グラフ深さ優先探索,連結成分,連結成分の数,幅優先探索,グラフ

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

「未探索」 ...

2020年3月20日その他区間和,区間,累積和,配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...

2020年3月20日その他

大きさが \(H × W\) の二次元配列 \(a\) 上において、 + a + … + a
+ a + a + … + a
+ …
+ a + a + … + ...

グラフ最大フロー・最小カット定理,カット,最小カット,競プロ,フロー,最大フロー,Ford-Fulkerson,フローネットワーク

アルゴリズム

最小カットの容量を求めるアルゴリズム:

フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
\(|f^*|\) が最小カットの容量

...

2020年3月20日グラフフロー,最大フロー,二部グラフ,最大マッチング,マッチング,競プロ

アルゴリズム

二部グラフの最大マッチングを求めるアルゴリズム:

二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G’\) を作る\(G\) にソース \(s\) ...

2020年3月19日グラフ最大フロー,Ford-Fulkerson,フローネットワーク,最大フロー・最小カット定理,競プロ,フロー

アルゴリズム

最大フローを求めるアルゴリズム(Ford-Fullkerson法):

フロー \(f\) を 0 としてはじめる
ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...

グラフフロー,フローネットワーク,用語・定義

フローフローとフローネットワーク

関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ(フローネットワーク) \(G=(V,E)\) 上で定義されます。

2020年3月16日グラフ,競プロ,LCA,ダブリング,木の2頂点間の距離,木のパス上に頂点があるか

最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。

頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...