Ebi-chan Lengthens Shortest Paths [RUPC2018 Day3 F]

前提知識

• ワーシャルフロイド
• 最大流問題

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753218

まず、長さを増やすかもしれない辺を考えてみると、これは最短路に含まれうる辺だけである。
それ以外の辺は最短距離に関係しない。
説明のため、「D[a][b] := aからbへの最短経路」とする。
ある辺iが最短路に含まれるかどうかは、D[s][u[i]] + d[i] + D[v[i]][t] = D[s][t]を満たすかで判断できる。
そのため、D[a][b]をワーシャルフロイドを使って計算しておこう。

有向グラフを最短路に含まれうる辺だけに残して考えてみると、今回の問題は丁度最小カット問題であることが分かる。
この辺の気づきが少し難しいのだが、最小カット問題について良く理解していることと頂点数がフロー向きになっていることから頑張って引っ張り出そう。
最小カットは最大流問題を解くことで計算できる。
Dを使ってある辺iが最短路に含まれうると分かったら、それを最大流問題で使おう。

int N, M, s, t;
int u[2020], v[2020], d[2020], c[2020];
int D[202][202];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> s >> t; s--; t--;

    rep(i, 0, N) rep(j, 0, N) D[i][j] = inf;
    rep(i, 0, N) D[i][i] = 0;

    rep(i, 0, M) {
        cin >> u[i] >> v[i] >> d[i] >> c[i];
        u[i]--; v[i]--;
        D[u[i]][v[i]] = d[i];
    }

    rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

    MaxFlow<int> mf;
    mf.init(N);
    rep(i, 0, M) {
        int a = u[i], b = v[i];
        if (D[s][a] + d[i] + D[b][t] == D[s][t]) mf.add_edge(a, b, c[i]);
    }

    int ans = mf.maxflow(s, t);
    cout << ans << endl;
}