最小費用流 @ C++

最小費用流実装した.

最小費用流のアルゴリズムは少なくとも3種類ぐらいある.

  • とりあえず,フローを求めてから,負閉路を頑張って消していく
  • 最小費用0フローからはじめて,augmenting shortest path で増やしていく
  • push, relabelの一般化(よく知らない)

2番目を実装した.

簡単のため,非負費用.

検証は UVa 10594 Data Flow.

適当に組んだら時間オーバーだったので,配列とか使って真面目に書いた.

本体は以下.非負費用というのが大きい.まず,f=0が最小費用0フローになっている.

よって,ポテンシャルの決定にベルマンフォードを実行しなくて良い.

ただ,単純にダイクストラでガンガン流していけば良い.

pair<bool, ll> successive_shortest_path() {
  typedef pair<ll, int> TV;
  FOR (i, N) FOR (j, N) f[i][j] = 0;
  fill_n(p, N, 0);
  for (ll df = D; D > 0; df = D -= df) {
    fill_n(d, N, INF);
    fill_n(q, N, -1); q[0] = 0;
    priority_queue<TV, vector<TV>, greater<TV> > que;
    que.push(TV(d[0] = 0, 0));
    for (int v = 0; !que.empty(); v = que.top().second) {
      que.pop();
      FOR (w, N) if (g[v][w]) {
        if (f[v][w] < K && d[v] + c[v][w] + p[v] - p[w] < d[w])
          q[w] = v, que.push(TV(d[w] = d[v] + c[v][w] + p[v] - p[w], w)), fw[w] = true;
        if (0 < f[w][v] && d[v] - c[w][v] - p[w] + p[v] < d[w])
          q[w] = v, que.push(TV(d[w] = d[v] - c[w][v] - p[w] + p[v], w)), fw[w] = false;
      }
    }
    if (q[N-1] < 0) return pair<bool, ll>(false, 0);
    for (int v = N-1; v != 0; v = q[v]) df = min(df, fw[v] ? K - f[q[v]][v]: f[v][q[v]]);
    for (int v = N-1; v != 0; v = q[v]) fw[v] ? f[q[v]][v] += df: f[v][q[v]] -= df;
    FOR (v, N) p[v] += d[v];
  }
  ll cost = 0;
  FOR (v, N) FOR (w, N) if (g[v][w]) cost += c[v][w] * f[v][w];
  return pair<bool, ll>(true, cost);
}

入出力とか合わせた全体.

// 10594    Data Flow   Accepted    C++ 0.384   2010-02-24 18:18:53
#include <iostream>
#include <queue>
#include <climits>

#define INF INT_MAX
#define FOR(i, n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

typedef long long int ll;
const int N_MAX = 100;
bool g[N_MAX][N_MAX], fw[N_MAX];
ll K, D, f[N_MAX][N_MAX], c[N_MAX][N_MAX], d[N_MAX];
int N, M, p[N_MAX], q[N_MAX];

pair<bool, ll> successive_shortest_path() {
  typedef pair<ll, int> TV;
  FOR (i, N) FOR (j, N) f[i][j] = 0;
  fill_n(p, N, 0);
  for (ll df = D; D > 0; df = D -= df) {
    fill_n(d, N, INF);
    fill_n(q, N, -1); q[0] = 0;
    priority_queue<TV, vector<TV>, greater<TV> > que;
    que.push(TV(d[0] = 0, 0));
    for (int v = 0; !que.empty(); v = que.top().second) {
      que.pop();
      FOR (w, N) if (g[v][w]) {
        if (f[v][w] < K && d[v] + c[v][w] + p[v] - p[w] < d[w])
          q[w] = v, que.push(TV(d[w] = d[v] + c[v][w] + p[v] - p[w], w)), fw[w] = true;
        if (0 < f[w][v] && d[v] - c[w][v] - p[w] + p[v] < d[w])
          q[w] = v, que.push(TV(d[w] = d[v] - c[w][v] - p[w] + p[v], w)), fw[w] = false;
      }
    }
    if (q[N-1] < 0) return pair<bool, ll>(false, 0);
    for (int v = N-1; v != 0; v = q[v]) df = min(df, fw[v] ? K - f[q[v]][v]: f[v][q[v]]);
    for (int v = N-1; v != 0; v = q[v]) fw[v] ? f[q[v]][v] += df: f[v][q[v]] -= df;
    FOR (v, N) p[v] += d[v];
  }
  ll cost = 0;
  FOR (v, N) FOR (w, N) if (g[v][w]) cost += c[v][w] * f[v][w];
  return pair<bool, ll>(true, cost);
}

int main() {
  while(true) {
    cin >> N >> M;
    if (cin.fail()) break;
    FOR (i, N) fill_n(g[i], N, false);
    FOR (i, M) {
      int t, h, w;
      cin >> t >> h >> w; --t, --h;
      g[t][h] = g[h][t] = true, c[t][h] = c[h][t] = w;
    }
    cin >> D >> K;
    pair<bool, ll> result = successive_shortest_path();
    if(result.first) cout << result.second << endl;
    else cout << "Impossible." << endl;
  }
}

ところで,計算量は?

ダイクストラの反復回数が分かれば良い.

反復回数は高々,最大流量.って評価がかなり甘い気がする.詳しいところは良く分からない(勉強不足で).

ただ,負閉路をどんどん消していくアルゴリズムは,負閉路をうまく選ぶ(枝あたりの平均重みが最小に

なるように選ぶ)と反復回数が |V| と |E| の多項式で押さえられるらしいから,

少なくとも組合せ的な強多項式時間アルゴリズムはある.しかし,計算量はあまり良くなかった記憶がある.