minimum_mean_cycle.hpp¶
Minimum mean edge weight among directed cycles by Karp's O(nm) dynamic program; nullopt means the graph is acyclic.
求有向带权图中平均边权最小的环；适合无限重复路径的最优长期平均代价。
Implementation¶
#ifndef NOYA_MINIMUM_MEAN_CYCLE_HPP
#define NOYA_MINIMUM_MEAN_CYCLE_HPP 1
/// @complexity Time: O(VE).
/// Space: O(V^2).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <optional>
#include <tuple>
#include <vector>
namespace noya {
/// @brief Minimum mean edge weight among directed cycles by Karp's O(nm)
/// dynamic program; nullopt means the graph is acyclic.
template <class Weight>
std::optional<long double>
minimum_mean_cycle(int n,
const std::vector<std::tuple<int, int, Weight>> &edges) {
assert(n >= 0);
const long double infinity = std::numeric_limits<long double>::infinity();
std::vector distance(n + 1, std::vector<long double>(n, infinity));
for (int vertex = 0; vertex < n; vertex++) {
distance[0][vertex] = 0;
}
for (int length = 1; length <= n; length++) {
for (auto [from, to, weight] : edges) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
if (distance[length - 1][from] != infinity) {
distance[length][to] = std::min(distance[length][to],
distance[length - 1][from] +
static_cast<long double>(weight));
}
}
}
long double answer = infinity;
for (int vertex = 0; vertex < n; vertex++) {
if (distance[n][vertex] == infinity) {
continue;
}
long double worst_prefix = -infinity;
for (int length = 0; length < n; length++) {
if (distance[length][vertex] != infinity) {
worst_prefix = std::max(
worst_prefix,
(distance[n][vertex] - distance[length][vertex]) / (n - length));
}
}
answer = std::min(answer, worst_prefix);
}
if (answer == infinity) {
return std::nullopt;
}
return answer;
}
} // namespace noya
#endif // NOYA_MINIMUM_MEAN_CYCLE_HPP
#include <algorithm>
#include <cassert>
#include <cmath>
#include <limits>
#include <optional>
#include <tuple>
#include <vector>
/// @complexity Time: O(VE).
/// Space: O(V^2).
namespace noya {
/// @brief Minimum mean edge weight among directed cycles by Karp's O(nm)
/// dynamic program; nullopt means the graph is acyclic.
template <class Weight>
std::optional<long double>
minimum_mean_cycle(int n,
const std::vector<std::tuple<int, int, Weight>> &edges) {
assert(n >= 0);
const long double infinity = std::numeric_limits<long double>::infinity();
std::vector distance(n + 1, std::vector<long double>(n, infinity));
for (int vertex = 0; vertex < n; vertex++) {
distance[0][vertex] = 0;
}
for (int length = 1; length <= n; length++) {
for (auto [from, to, weight] : edges) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
if (distance[length - 1][from] != infinity) {
distance[length][to] = std::min(distance[length][to],
distance[length - 1][from] +
static_cast<long double>(weight));
}
}
}
long double answer = infinity;
for (int vertex = 0; vertex < n; vertex++) {
if (distance[n][vertex] == infinity) {
continue;
}
long double worst_prefix = -infinity;
for (int length = 0; length < n; length++) {
if (distance[length][vertex] != infinity) {
worst_prefix = std::max(
worst_prefix,
(distance[n][vertex] - distance[length][vertex]) / (n - length));
}
}
answer = std::min(answer, worst_prefix);
}
if (answer == infinity) {
return std::nullopt;
}
return answer;
}
} // namespace noya