minimum_mean_cycle.hpp¶

SECTIONGraph INCLUDEnoya/minimum_mean_cycle.hpp

求有向带权图中平均边权最小的环；适合无限重复路径的最优长期平均代价。

Complexity: Time: O(VE). Space: O(V^2).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @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>> &es) {
  assert(n >= 0);
  const long double inf = std::numeric_limits<long double>::infinity();
  std::vector dis(n + 1, std::vector<long double>(n, inf));
  for (int u = 0; u < n; u++) {
    dis[0][u] = 0;
  }
  for (int len = 1; len <= n; len++) {
    for (auto [u1, to, w] : es) {
      assert(0 <= u1 && u1 < n);
      assert(0 <= to && to < n);
      if (dis[len - 1][u1] != inf) {
        dis[len][to] = std::min(dis[len][to],
                                dis[len - 1][u1] + static_cast<long double>(w));
      }
    }
  }
  long double ans = inf;
  for (int u = 0; u < n; u++) {
    if (dis[n][u] == inf) {
      continue;
    }
    long double wp = -inf;
    for (int len = 0; len < n; len++) {
      if (dis[len][u] != inf) {
        wp = std::max(wp, (dis[n][u] - dis[len][u]) / (n - len));
      }
    }
    ans = std::min(ans, wp);
  }
  if (ans == inf) {
    return std::nullopt;
  }
  return ans;
}

} // namespace noya

#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>> &es) {
  assert(n >= 0);
  const long double inf = std::numeric_limits<long double>::infinity();
  std::vector dis(n + 1, std::vector<long double>(n, inf));
  for (int u = 0; u < n; u++) {
    dis[0][u] = 0;
  }
  for (int len = 1; len <= n; len++) {
    for (auto [u1, to, w] : es) {
      assert(0 <= u1 && u1 < n);
      assert(0 <= to && to < n);
      if (dis[len - 1][u1] != inf) {
        dis[len][to] = std::min(dis[len][to],
                                dis[len - 1][u1] + static_cast<long double>(w));
      }
    }
  }
  long double ans = inf;
  for (int u = 0; u < n; u++) {
    if (dis[n][u] == inf) {
      continue;
    }
    long double wp = -inf;
    for (int len = 0; len < n; len++) {
      if (dis[len][u] != inf) {
        wp = std::max(wp, (dis[n][u] - dis[len][u]) / (n - len));
      }
    }
    ans = std::min(ans, wp);
  }
  if (ans == inf) {
    return std::nullopt;
  }
  return ans;
}

} // 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>> &es) {
  assert(n >= 0);
  const long double inf = std::numeric_limits<long double>::infinity();
  std::vector dis(n + 1, std::vector<long double>(n, inf));
  for (int u = 0; u < n; u++) {
    dis[0][u] = 0;
  }
  for (int len = 1; len <= n; len++) {
    for (auto [u1, to, w] : es) {
      assert(0 <= u1 && u1 < n);
      assert(0 <= to && to < n);
      if (dis[len - 1][u1] != inf) {
        dis[len][to] = std::min(dis[len][to],
                                dis[len - 1][u1] + static_cast<long double>(w));
      }
    }
  }
  long double ans = inf;
  for (int u = 0; u < n; u++) {
    if (dis[n][u] == inf) {
      continue;
    }
    long double wp = -inf;
    for (int len = 0; len < n; len++) {
      if (dis[len][u] != inf) {
        wp = std::max(wp, (dis[n][u] - dis[len][u]) / (n - len));
      }
    }
    ans = std::min(ans, wp);
  }
  if (ans == inf) {
    return std::nullopt;
  }
  return ans;
}

} // namespace noya