ぼくの考えたさいきょうのフローライブラリ

要約 "最小費用流" のライブラリを "最小費用最大流" ではなく "最小費用 $\vecb$-フロー" の形で書くことについて. 「さいきょう」であって「さいそく」ではない. よくある実装に少し手を加えることで, 入力として扱える問題の範囲を広くでき, ライブラリ使用毎にアドホック気味に書く部分を減らせる. イントロ 最小費用流問題と呼ばれる問題を解く際, 競技プログラミングでは, 蟻本 に記載のものをはじめ多くの場合, 最小費用最大流を解くライブラリ, 特に最短路反復法や Primal-Dual 法 1 と呼ばれる実装が用いられる. これらのアルゴリズムを使う際, 辺コストが負になりうる場合, 負サイクルがある場合, 最小流量制約がある場合, 頂点吸込みや湧出しがある場合などは, Bellman-Ford 法や SPFA 等で追加処理を行ったり, ネットワークの変形をすることで, 同値