noshi91のメモ

データ構造のある風景

2021-12-15から1日間の記事一覧

容量下限などが付いている最小費用流

概要 辺の流量に下限があったりする最小費用流を、思いつく範囲で一般化してみました。 記法の定義 を有向グラフとします。 フロー に対して、その境界 を で定義します。 つまり、境界は各頂点から流れ出る量を表しています。 ベクトルに対して不等号を使っ…