前提 基本的な考えは、Bellman-Ford法による最小費用流の求め方と同じである。 以下の実装では高速化のためBellman-Ford法の実装個所をDijkstra法に置き換えており、同時に負の辺が存在するグラフに対してDijkstra法を適用するため、ポテンシャルを導入して…

前提 最小費用流問題のグラフには、最大流問題で与えられる辺の情報に加えて辺のコストが付与される。 以下の実装では、このコストに対してS-T最短路を1つ見つけて目いっぱい流す、その経路が限界になったら次の最短路を見つけて目いっぱい流して、という事…