C++ Library for Competitive Programming
/*
* @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;
}