競プロノート

Appearance

最小費用流（Minimum Cost Flow） ​

容量とコストを持つ有向グラフにおいて、指定した流量を最小コストで流す問題。

特徴 ​

項目内容
用途最小コストの輸送・割当
適用条件ACLでは容量・コストが非負
代表的な解法最短路反復法（ポテンシャル利用）
計算量O(F(V+E) log(V+E))

Fは流量、Vは頂点数、Eは辺数。

考え方 ​

各辺には次の情報がある。

  • cap：流せる量の上限
  • cost：1単位流すためのコスト

辺にx単位流すと、その辺の費用は x * cost となる。

始点sから終点tに指定量Fを流すとき、全辺の費用の合計を最小化する。

代表的な解法では、残余グラフ上で最短路を見つけ、流量を増やす操作を繰り返す。

逆辺を利用することで、以前流したフローを変更することもできる。

実装（ACL） ​

cpp

#include <bits/stdc++.h>

#include <atcoder/mincostflow>
using namespace std;
using namespace atcoder;
using ll = long long;

int main() {
    int n, m, s, t, f;
    cin >> n >> m >> s >> t >> f;

    mcf_graph<int, ll> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, cap;
        ll cost;
        cin >> u >> v >> cap >> cost;
        g.add_edge(u, v, cap, cost);
    }

    auto [flow, cost] = g.flow(s, t, f);
    if (flow < f) cout << -1 << '\n';
    else cout << cost << '\n';
}

使用例 ​

入力（0-indexed、有向グラフ）

各辺は from to cap cost の順に与える。

text
4 5 0 3 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1

出力

text
6

2単位流すとき、例えば次の2経路を利用できる。

  • 0 → 1 → 2 → 3：コスト3
  • 0 → 2 → 3：コスト3

合計の最小費用は6。

ACLの主な操作 ​

メソッド機能
add_edge(u, v, cap, cost)容量・コスト付き有向辺を追加
flow(s, t)最大流量と、その流量の最小費用
flow(s, t, f)最大f単位まで流し、流量と費用を返す
slope(s, t)流量と最小費用の関係を取得
get_edge(i)i番目の辺の情報を取得
edges()全辺の情報を取得

指定量を流せるか判定 ​

flow(s, t, f) は、流せる量がf未満の場合もある。

cpp
auto [flow, cost] = g.flow(s, t, f);

if (flow != f) {
    // f単位流せない
} else {
    // costがf単位の最小費用
}

実際に流した辺を取得 ​

cpp
auto [flow, cost] = g.flow(s, t, f);

for (auto e : g.edges()) {
    if (e.flow == 0) continue;
    cout << e.from << " " << e.to << " " << e.flow << '\n';
}

各辺のflowに実際に流した量が入っている。

slope（流量と費用の関係） ​

slope() を使うと、流量を変化させたときの最小費用が得られる。

cpp
auto points = g.slope(s, t);

for (auto [flow, cost] : points) {
    cout << flow << " " << cost << '\n';
}

返り値は (流量, 最小費用) の折れ線の折れ点。

  • 最初の要素は (0, 0)。
  • 流量に対する最小費用は下に凸になる。
  • 同一直線上の中間点は省略される。
  • 各整数流量の費用は折れ線から求められる。

flow() と slope() は、同じグラフに対して繰り返し呼び出さない。

最大化問題への応用 ​

ACLでは負のコストを直接指定できない。

利益を最大化したい場合、例えば

cost = C - profit

と変換して最小化する。

各解が同じ本数の利益付き辺を使用する場合、定数Cを加えても最適解は変わらない。

この性質は二部割当問題などで利用できる。

ただし、解によって通る辺数が異なる場合、すべての辺に定数を加えると最適解が変わることがあるので注意。

注意点 ​

  • ACLでは辺の容量・コストは0以上。
  • flow(s, t, f) はf単位流せることを保証しない。
  • flow(s, t) は流せる最大流量を求め、その流量に対する費用を最小化する。
  • ACLの最小費用流では flow() と slope() を合わせて複数回呼べない。
  • コストの総和が型の範囲を超えないようにする。
  • s と t は異なる頂点である必要がある。
  • 最大フローよりも計算量が大きくなりやすい。
  • 利益最大化では、コストの変換方法に注意する。

関連 ​