C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title グラフ/フロー/最小費用流/最小費用 $s$-$t$-フロー 最短路反復法版(最小費用最大流) * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1088 */ #include <algorithm> #include <iostream> #include <iterator> #include <utility> #include <vector> #include "emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" int main() { struct Train { int x, y, c; }; while (true) { int n; std::cin >> n; if (n == 0) break; int num = 0; std::vector<std::vector<Train>> trains(n - 1); std::vector<std::vector<int>> times(n - 1); for (int i = 0; i < n - 1; ++i) { int m; std::cin >> m; num += m; while (m--) { int x, y, c; std::cin >> x >> y >> c; trains[i].emplace_back(Train{x, y, c}); times[i].emplace_back(y); } std::sort(times[i].begin(), times[i].end()); times[i].erase(std::unique(times[i].begin(), times[i].end()), times[i].end()); num += times[i].size() * 2; } emthrm::MinimumCostSTFlow<int, long long> minimum_cost_flow(num + 2); const int s = num, t = num + 1; for (int i = 0; std::cmp_less(i, trains.front().size()); ++i) { minimum_cost_flow.add_edge(s, i, 1, 0); } int w = 0; for (int i = 0; i < n - 1; ++i) { int m = trains[i].size(); for (int j = 0; j < m; ++j) { const int idx = std::distance( times[i].begin(), std::lower_bound(times[i].begin(), times[i].end(), trains[i][j].y)); minimum_cost_flow.add_edge(j + w, idx + w + m, 1, trains[i][j].c); } w += m; m = times[i].size(); for (int j = 0; j < m; ++j) { minimum_cost_flow.add_edge(j + w, j + w + m, 1, 0); } w += m; if (i + 1 < n - 1) { for (int j = 0; j < m; ++j) { for (int k = 0; std::cmp_less(k, trains[i + 1].size()); ++k) { if (times[i][j] <= trains[i + 1][k].x) { minimum_cost_flow.add_edge(j + w, k + w + m, 1, 0); } } } w += m; } } for (int i = num - times.back().size(); i < num; ++i) { minimum_cost_flow.add_edge(i, t, 1, 0); } int g; std::cin >> g; const auto [ans_class, ans_fare] = minimum_cost_flow.minimum_cost_maximum_flow(s, t, g); std::cout << ans_class << ' ' << ans_fare << '\n'; } return 0; }
#line 1 "test/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.3.test.cpp" /* * @title グラフ/フロー/最小費用流/最小費用 $s$-$t$-フロー 最短路反復法版(最小費用最大流) * * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1088 */ #include <algorithm> #include <iostream> #include <iterator> #include <utility> #include <vector> #line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" #line 5 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" #include <cassert> #include <functional> #include <limits> #include <queue> #line 11 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp" namespace emthrm { template <typename T, typename U> struct MinimumCostSTFlow { 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 MinimumCostSTFlow(const int n, const U uinf = std::numeric_limits<U>::max()) : uinf(uinf), graph(n), tinf(std::numeric_limits<T>::max()), n(n), has_negative_edge(false), prev_v(n, -1), prev_e(n, -1), dist(n), potential(n, 0) {} void add_edge(const int src, const int dst, const T cap, const U cost) { has_negative_edge |= cost < 0; graph[src].emplace_back(dst, cap, cost, graph[dst].size()); graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1); } U solve(const int s, const int t, T flow) { if (flow == 0) [[unlikely]] return 0; U res = 0; has_negative_edge ? bellman_ford(s) : dijkstra(s); while (true) { if (dist[t] == uinf) return uinf; res += calc(s, t, &flow); if (flow == 0) break; dijkstra(s); } return res; } U solve(const int s, const int t) { U res = 0; T flow = tinf; bellman_ford(s); while (potential[t] < 0 && dist[t] != uinf) { res += calc(s, t, &flow); dijkstra(s); } return res; } std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t, const T flow) { if (flow == 0) [[unlikely]] return {0, 0}; T f = flow; U cost = 0; has_negative_edge ? bellman_ford(s) : dijkstra(s); while (dist[t] != uinf) { cost += calc(s, t, &f); if (f == 0) break; dijkstra(s); } return {flow - f, cost}; } private: const T tinf; const int n; bool has_negative_edge; std::vector<int> prev_v, prev_e; std::vector<U> dist, potential; std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>, std::greater<std::pair<U, int>>> que; void bellman_ford(const int s) { std::fill(dist.begin(), dist.end(), uinf); dist[s] = 0; bool is_updated = true; for (int step = 0; step < n && is_updated; ++step) { is_updated = false; for (int i = 0; i < n; ++i) { if (dist[i] == uinf) continue; for (int j = 0; std::cmp_less(j, graph[i].size()); ++j) { const Edge& e = graph[i][j]; if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) { dist[e.dst] = dist[i] + e.cost; prev_v[e.dst] = i; prev_e[e.dst] = j; is_updated = true; } } } } assert(!is_updated); for (int i = 0; i < n; ++i) { if (dist[i] != uinf) potential[i] += dist[i]; } } void dijkstra(const int s) { std::fill(dist.begin(), dist.end(), uinf); dist[s] = 0; que.emplace(0, s); while (!que.empty()) { const auto [d, ver] = que.top(); que.pop(); if (dist[ver] < d) 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); } } } for (int i = 0; i < n; ++i) { if (dist[i] != uinf) potential[i] += dist[i]; } } U calc(const int s, const int t, T* flow) { T f = *flow; for (int v = t; v != s; v = prev_v[v]) { f = std::min(f, graph[prev_v[v]][prev_e[v]].cap); } *flow -= f; for (int v = t; v != s; v = prev_v[v]) { Edge& e = graph[prev_v[v]][prev_e[v]]; e.cap -= f; graph[v][e.rev].cap += f; } return potential[t] * f; } }; } // namespace emthrm #line 14 "test/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.3.test.cpp" int main() { struct Train { int x, y, c; }; while (true) { int n; std::cin >> n; if (n == 0) break; int num = 0; std::vector<std::vector<Train>> trains(n - 1); std::vector<std::vector<int>> times(n - 1); for (int i = 0; i < n - 1; ++i) { int m; std::cin >> m; num += m; while (m--) { int x, y, c; std::cin >> x >> y >> c; trains[i].emplace_back(Train{x, y, c}); times[i].emplace_back(y); } std::sort(times[i].begin(), times[i].end()); times[i].erase(std::unique(times[i].begin(), times[i].end()), times[i].end()); num += times[i].size() * 2; } emthrm::MinimumCostSTFlow<int, long long> minimum_cost_flow(num + 2); const int s = num, t = num + 1; for (int i = 0; std::cmp_less(i, trains.front().size()); ++i) { minimum_cost_flow.add_edge(s, i, 1, 0); } int w = 0; for (int i = 0; i < n - 1; ++i) { int m = trains[i].size(); for (int j = 0; j < m; ++j) { const int idx = std::distance( times[i].begin(), std::lower_bound(times[i].begin(), times[i].end(), trains[i][j].y)); minimum_cost_flow.add_edge(j + w, idx + w + m, 1, trains[i][j].c); } w += m; m = times[i].size(); for (int j = 0; j < m; ++j) { minimum_cost_flow.add_edge(j + w, j + w + m, 1, 0); } w += m; if (i + 1 < n - 1) { for (int j = 0; j < m; ++j) { for (int k = 0; std::cmp_less(k, trains[i + 1].size()); ++k) { if (times[i][j] <= trains[i + 1][k].x) { minimum_cost_flow.add_edge(j + w, k + w + m, 1, 0); } } } w += m; } } for (int i = num - times.back().size(); i < num; ++i) { minimum_cost_flow.add_edge(i, t, 1, 0); } int g; std::cin >> g; const auto [ans_class, ans_fare] = minimum_cost_flow.minimum_cost_maximum_flow(s, t, g); std::cout << ans_class << ' ' << ans_fare << '\n'; } return 0; }