cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: グラフ/フロー/最小費用流/最小流量制約付き最小費用流
(test/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.test.cpp)

Depends on

Code

/*
 * @title グラフ/フロー/最小費用流/最小流量制約付き最小費用流
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230
 */

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp"
#include "emthrm/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.hpp"

int main() {
  constexpr int INF = std::numeric_limits<int>::max();
  int n, m;
  std::cin >> n >> m;
  emthrm::MinimumCostFlowWithLowerBoundConstraint<
      emthrm::MinimumCostBFlow, long long, long long>
          lower_bound_constraint(n, INF);
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  while (m--) {
    int x, y, s;
    std::cin >> x >> y >> s;
    lower_bound_constraint.add_edge(y, x, 1, INF, -s);
    graph[x].emplace_back(x, y, s);
  }
  std::vector<long long> dp(n, 0);
  for (int i = n - 2; i >= 0; --i) {
    for (const emthrm::Edge<int>& e : graph[i]) {
      dp[i] = std::max(dp[i], dp[e.dst] + e.cost);
    }
  }
  lower_bound_constraint.add_edge(0, n - 1, 0, INF, dp[0]);
  std::cout << lower_bound_constraint.solve(0, 0, 0) << '\n';
  return 0;
}
#line 1 "test/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.test.cpp"
/*
 * @title グラフ/フロー/最小費用流/最小流量制約付き最小費用流
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230
 */

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp"



#line 5 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp"
#include <cassert>
#include <functional>
#line 8 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp"
#include <numeric>
#include <queue>
#include <utility>
#line 12 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp"

namespace emthrm {

template <typename T, typename U>
struct MinimumCostBFlow {
  struct Edge {
    int dst, rev;
    T cap;
    U cost;
    explicit Edge(const int dst, const T cap, const U cost, const int rev)
        : dst(dst), rev(rev), cap(cap), cost(cost) {}
  };

  const U uinf;
  std::vector<std::vector<Edge>> graph;

  explicit MinimumCostBFlow(const int n,
                            const U uinf = std::numeric_limits<U>::max())
      : uinf(uinf), graph(n + 2), n(n), res(0), b(n + 2, 0) {}

  void add_edge(int src, int dst, const T cap, U cost) {
    if (cost < 0) {
      b[src] -= cap;
      b[dst] += cap;
      res += cost * cap;
      std::swap(src, dst);
      cost = -cost;
    }
    graph[src].emplace_back(dst, cap, cost, graph[dst].size());
    graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
  }

  void supply_or_demand(const int ver, const T amount) { b[ver] += amount; }

  U solve() {
    assert(std::reduce(b.begin(), b.end(), static_cast<T>(0)) == 0);
    T flow = 0;
    for (int i = 0; i < n; ++i) {
      if (b[i] > 0) {
        add_edge(n, i, b[i], 0);
        flow += b[i];
      } else if (b[i] < 0) {
        add_edge(i, n + 1, -b[i], 0);
      }
    }
    std::vector<int> prev_v(n + 2, -1), prev_e(n + 2, -1);
    std::vector<U> dist(n + 2), potential(n + 2, 0);
    std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
                        std::greater<std::pair<U, int>>> que;
    while (flow > 0) {
      std::fill(dist.begin(), dist.end(), uinf);
      dist[n] = 0;
      que.emplace(0, n);
      while (!que.empty()) {
        const auto [d, ver] = que.top();
        que.pop();
        if (d > dist[ver]) continue;
        for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
          const Edge& e = graph[ver][i];
          const U nxt = dist[ver] + e.cost + potential[ver] - potential[e.dst];
          if (e.cap > 0 && dist[e.dst] > nxt) {
            dist[e.dst] = nxt;
            prev_v[e.dst] = ver;
            prev_e[e.dst] = i;
            que.emplace(dist[e.dst], e.dst);
          }
        }
      }
      if (dist[n + 1] == uinf) return uinf;
      for (int i = 0; i < n + 2; ++i) {
        if (dist[i] != uinf) potential[i] += dist[i];
      }
      T f = flow;
      for (int v = n + 1; v != n; v = prev_v[v]) {
        f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
      }
      flow -= f;
      res += potential[n + 1] * f;
      for (int v = n + 1; v != n; v = prev_v[v]) {
        Edge& e = graph[prev_v[v]][prev_e[v]];
        e.cap -= f;
        graph[v][e.rev].cap += f;
      }
    }
    return res;
  }

  U solve(const int s, const int t, const T flow) {
    supply_or_demand(s, flow);
    supply_or_demand(t, -flow);
    return solve();
  }

 private:
  int n;
  U res;
  std::vector<T> b;
};

}  // namespace emthrm


#line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.hpp"



#include <concepts>
#line 7 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.hpp"

namespace emthrm {

template <template <typename, typename> class C, typename T, typename U>
requires requires (C<T, U> mcf) {
  {mcf.add_edge(std::declval<int>(), std::declval<int>(),
                std::declval<T>(), std::declval<U>())}
      -> std::same_as<void>;
  {mcf.solve(std::declval<int>(), std::declval<int>(), std::declval<T>())}
      -> std::same_as<U>;
}
struct MinimumCostFlowWithLowerBoundConstraint {
  const U uinf;

  explicit MinimumCostFlowWithLowerBoundConstraint(
      const int n, const U m, const U uinf = std::numeric_limits<U>::max())
      : uinf(uinf), m(m), sum_lb(0), mcf(n, uinf) {}

  void add_edge(const int src, const int dst, const T lb, const T ub,
                const U cost) {
    mcf.add_edge(src, dst, ub - lb, cost);
    mcf.add_edge(src, dst, lb, cost - m);
    sum_lb += lb;
  }

  U solve(const int s, const int t, const T flow) {
    const U tmp = mcf.solve(s, t, flow);
    return tmp == uinf ? uinf : tmp + m * sum_lb;
  }

 private:
  const U m;
  T sum_lb;
  C<T, U> mcf;
};

}  // namespace emthrm


#line 15 "test/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.test.cpp"

int main() {
  constexpr int INF = std::numeric_limits<int>::max();
  int n, m;
  std::cin >> n >> m;
  emthrm::MinimumCostFlowWithLowerBoundConstraint<
      emthrm::MinimumCostBFlow, long long, long long>
          lower_bound_constraint(n, INF);
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  while (m--) {
    int x, y, s;
    std::cin >> x >> y >> s;
    lower_bound_constraint.add_edge(y, x, 1, INF, -s);
    graph[x].emplace_back(x, y, s);
  }
  std::vector<long long> dp(n, 0);
  for (int i = n - 2; i >= 0; --i) {
    for (const emthrm::Edge<int>& e : graph[i]) {
      dp[i] = std::max(dp[i], dp[e.dst] + e.cost);
    }
  }
  lower_bound_constraint.add_edge(0, n - 1, 0, INF, dp[0]);
  std::cout << lower_bound_constraint.solve(0, 0, 0) << '\n';
  return 0;
}
Back to top page