flow_interpolate.hpp

View this file on GitHub
Last update: 2024-06-03 04:10:09+09:00
Include: #include "flow_interpolate.hpp"

Code

template <typename Cap, typename Cost>
vector<Cost> interpolate_slope(vector<pair<Cap, Cost>> slope) {
    vector<Cost> res(slope.back().first + 1);

    int n = slope.size();
    for (auto [cap, cost] : slope) res[cap] = cost;
    for (int i = 0; i < n - 1; ++i) {
        int l = slope[i].first, r = slope[i + 1].first;
        for (int j = l + 1; j < r; ++j) {
            res[j] = (res[l] * (r - j) + res[r] * (j - l)) / (r - l);
        }
    }

    return res;
}

#line 1 "flow_interpolate.hpp"
template <typename Cap, typename Cost>
vector<Cost> interpolate_slope(vector<pair<Cap, Cost>> slope) {
    vector<Cost> res(slope.back().first + 1);

    int n = slope.size();
    for (auto [cap, cost] : slope) res[cap] = cost;
    for (int i = 0; i < n - 1; ++i) {
        int l = slope[i].first, r = slope[i + 1].first;
        for (int j = l + 1; j < r; ++j) {
            res[j] = (res[l] * (r - j) + res[r] * (j - l)) / (r - l);
        }
    }

    return res;
}