最小費用流 @ 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| の多項式で押さえられるらしいから，

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

コンテンツ