2021-02-26から1日間の記事一覧
前提 最大流問題とは、辺に capacity を持つグラフが与えられて、始点から目いっぱい水を流した時に終点に流せる最大量を求める問題。 グラフの最大流は、そのグラフのS-T最小カットに対応する。 計算量: O(|flow||E|) (最大フローをflow、辺数をEとする) …
前提 最大流問題とは、辺に capacity を持つグラフが与えられて、始点から目いっぱい水を流した時に終点に流せる最大量を求める問題。 グラフの最大流は、そのグラフのS-T最小カットに対応する。 計算量: O(|flow||E|) (最大フローをflow、辺数をEとする) …