フォード-ファルカーソン法は、最小フロー問題を解くアルゴリズムのひとつである。 目次 アルゴリズムの説明 計算量 コード アルゴリズムの説明 このアルゴリズムを説明する前に、残余ネットワークの説明をする。残余ネットワークとは、現状での流すことができる量をコストとした有向グラフのことである。 以下の図を例にとる。左の図は、ネットワークフローを示す。辺に書いてある数字は、現在流してる量/許容量を示す。この時の残余ネットワークは右の図になる。 茶色の数字と黒い数字を足した値が許容量となり、黒い数字が現在流している量を示す。 フォードファルカーソン法では、残余ネットワークを用いて最適解を導く。 ネットワークフローから残余ネットワークを作成する。 残余ネットワークにおいて、SからTへ向かうルートがあるか探索する。ルートが存在しない場合は、終了する。 残余ネットワークを用いて、SからTへの最大流量を求