C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @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; }