AOJ 2691 - Cost Performance Flow

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2691

解法

流量1ずつ流していったときの最小費用流のコストのグラフは、下に凸な折れ線グラフになる。
求める値は、このグラフと点 $(M, 0)$ との距離であり、グラフの形からこの距離も下に凸な関数となる。
なので、折れ線の各線分に対して $(M, 0)$ との距離関数を求め、極値を計算する。

今流量を $f_i$ だけ流しており、その時の最小コストが $S_i$ であるとする。
この状態から、追加で 1 流すとしたときのコストを $c_i$ とする。
$f_i$ の代わりに $f_i + \Delta ~~(0 \leq \Delta \leq 1)$ 流すとすると、その時のコスパは $$(M - f_i - \Delta)^2 + (S_i + c_i\Delta)^2$$ である。
これを微分して極値を得る $\Delta$ を求めると $$\Delta = \frac{M - f_i - S_i c_i}{c_i^2 + 1}$$ となる。
これが 0 以上 1 以下なら、候補になる。
これらの候補と折れ線の端点の中で一番小さいコストが求める値である。

ところで、適当に実装すると（有理数部分で）オーバーフローするため、頑張ってオーバーフローしないようにするか、int128 を使ってごまかそう。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = __int128;

// めっちゃ長いのでライブラリ部分は省略

int main() {
    int n, m; cin >> n >> m;
    capacity_weighted_graph<int, int> g(n);
    int s, t; cin >> s >> t;
    s--, t--;
    for(int i = 0; i < m; ++i) {
        int a, b, u, c; cin >> a >> b >> u >> c;
        add_edge(g, a - 1, b - 1, u, c);
    }

    const ll M = [&] { auto tmp = g; return max_flow(tmp, s, t); }();

    rational<ll> ans{M * M, 1};
    auto calc_cost = [&] (ll fi, ll ci, ll ci_sum, rational<ll> delta) {
        const auto a = M - (fi + delta), b = ci_sum + ci * delta;
        return a * a + b * b;
    };
    ll ci_sum = 0;
    for(int i = 0; i < M; ++i) {
        const ll ci = min_cost_flow(g, s, t, 1);
        if(0 <= M - i - ci * ci_sum && M - i - ci * ci_sum <= ci * ci + 1) {
            auto delta = rational<ll>{M - i - ci * ci_sum, ci * ci + 1};
            delta.reduce();
            ans = min(ans, calc_cost(i, ci, ci_sum, delta));
        }
        ci_sum += ci;
        ans = min(ans, calc_cost(i + 1, 0, ci_sum, rational<ll>{0, 1}));
    }

    cout << (long long)ans.numerator() << "/" << (long long)ans.denominator() << endl;
}

感想

オーバーフローが罠すぎる（なんか雑に gcd 取るだけだったらオーバーフローした）。