グラフ競プロ,フロー,最大フロー,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\) が残余ネットワーク \ ...