Enumerate Monge d-edge shortest path
(algorithm/enumerate_monge_d_edge_shortest_path.hpp)

• View this file on GitHub
• Last update: 2023-11-08 15:46:57+09:00
• Include: #include "algorithm/enumerate_monge_d_edge_shortest_path.hpp"

説明

辺の重みがMongeであるようなグラフに対して $0$ からスタートして、 $N-1$ へちょうど $d$ 辺使った場合の最短路の値を $d = 1, 2, \dots, N-1$ について求める。 $O(N^2 \log N)$

Depends on

• Monotone Minima (algorithm/monotone_minima.hpp)

Verified with

• test/yuki/yuki_952.test.cpp

Code

#pragma once

#include <limits>
#include <utility>
#include <vector>

#include "../algorithm/monotone_minima.hpp"

namespace ebi {

template <class F, class T = decltype(std::declval<F>()(std::declval<int>(),
                                                        std::declval<int>()))>
std::vector<T> enumerate_monge_d_edge_shortest_path(int n, F f) {
    const T max = std::numeric_limits<T>::max();
    std::vector<T> res(n, max);
    std::vector<T> dp(n, max);
    dp[0] = 0;
    auto g = [&](int j, int i) -> T {
        if (dp[i] == max || i >= j) return max;
        return dp[i] + f(i, j);
    };
    for (int d = 1; d < n; d++) {
        std::vector<int> argmin = monotone_minima(n, n, g).first;
        for (int i = n - 1; i >= d; i--) dp[i] = g(i, argmin[i]);
        res[d] = dp[n - 1];
    }
    return res;
}

}  // namespace ebi

#line 2 "algorithm/enumerate_monge_d_edge_shortest_path.hpp"

#include <limits>
#include <utility>
#include <vector>

#line 2 "algorithm/monotone_minima.hpp"

#include <functional>
#line 6 "algorithm/monotone_minima.hpp"

namespace ebi {

template <class F,
          class T = decltype(std::declval<F>()(std::declval<int>(),
                                               std::declval<int>())),
          class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left,
                   int right) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid]);
        self(self, mid + 1, bottom, argmin[mid], right);
    };
    dfs(dfs, 0, n - 1, 0, m - 1);
    return {argmin, min_val};
}

template <class T, class F, class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> slide_monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left, int right,
                   int depth) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left, depth);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i, depth);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid], depth + 1);
        self(self, mid + 1, bottom, argmin[mid], right, depth + 1);
    };
    dfs(dfs, 0, n - 1, 0, m - 1, 0);
    return {argmin, min_val};
}

}  // namespace ebi
#line 8 "algorithm/enumerate_monge_d_edge_shortest_path.hpp"

namespace ebi {

template <class F, class T = decltype(std::declval<F>()(std::declval<int>(),
                                                        std::declval<int>()))>
std::vector<T> enumerate_monge_d_edge_shortest_path(int n, F f) {
    const T max = std::numeric_limits<T>::max();
    std::vector<T> res(n, max);
    std::vector<T> dp(n, max);
    dp[0] = 0;
    auto g = [&](int j, int i) -> T {
        if (dp[i] == max || i >= j) return max;
        return dp[i] + f(i, j);
    };
    for (int d = 1; d < n; d++) {
        std::vector<int> argmin = monotone_minima(n, n, g).first;
        for (int i = n - 1; i >= d; i--) dp[i] = g(i, argmin[i]);
        res[d] = dp[n - 1];
    }
    return res;
}

}  // namespace ebi

Back to top page