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

2番目を実装した．

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

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

```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| の多項式で押さえられるらしいから，