test/yosupo/min_cost_b_flow.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/min_cost_b_flow

Depends on

• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)
• ネットワーク単体法 (src/Optimization/NetworkSimplex.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_cost_b_flow
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Optimization/NetworkSimplex.hpp"
using namespace std;
ostream &operator<<(ostream &stream, const __int128_t &v) {
 if (v == 0) stream << "0";
 __int128_t tmp;
 if (v < 0) stream << "-", tmp= -v;
 else tmp= v;
 std::string s;
 while (tmp) s+= '0' + (tmp % 10), tmp/= 10;
 return std::reverse(s.begin(), s.end()), stream << s;
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using MCF= NetworkSimplex<long long, long long>;
 int N, M;
 cin >> N >> M;
 MCF graph(N);
 vector<MCF::EdgePtr> edges;
 for (int i= 0; i < N; i++) {
  long long b;
  cin >> b;
  graph.add_supply(i, b);
 }
 for (int i= 0; i < M; i++) {
  long long s, t, l, u, c;
  cin >> s >> t >> l >> u >> c;
  edges.emplace_back(graph.add_edge(s, t, l, u, c));
 }
 if (graph.b_flow()) {
  cout << graph.get_result_value<__int128_t>() << '\n';
  for (int i= 0; i < N; i++) cout << graph.get_potential(i) << '\n';
  for (auto &e: edges) cout << e.flow() << '\n';
 } else {
  cout << "infeasible" << '\n';
 }
 return 0;
}

#line 1 "test/yosupo/min_cost_b_flow.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_cost_b_flow
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Optimization/NetworkSimplex.hpp"
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <cstdint>
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/NetworkSimplex.hpp"
template <typename flow_t, typename cost_t, MinMaxEnum obj= MINIMIZE> class NetworkSimplex {
 struct Node {
  int par, pred;
  flow_t sup;
  cost_t pi;
 };
 struct Edge {
  int u, v;
  flow_t low, up, flow;
  cost_t cost;
  int8_t state= 1;
 };
 int n, m= 0;
 std::vector<Node> ns;
 std::vector<Edge> es;
 std::vector<int> bfs, next, prev;
 inline void link(int u, int v) { next[u]= v, prev[v]= u; }
 inline void link(int u, int v, int w) { link(u, v), link(v, w); }
 inline auto opp_cost(int e) const { return es[e].cost + ns[es[e].u].pi - ns[es[e].v].pi; }
 inline void pivot(int in_arc) {
  int u_in= es[in_arc].u, v_in= es[in_arc].v, u, e, a= u_in, b= v_in;
  while (a != b) a= ns[a].par == -1 ? v_in : ns[a].par, b= ns[b].par == -1 ? u_in : ns[b].par;
  if (es[in_arc].state == -1) std::swap(u_in, v_in);
  int lca= a, side= 0, u_out= -1, i= 0, S= 0;
  flow_t delta= es[in_arc].up;
  for (u= u_in; u != lca && delta > 0; u= ns[u].par) {
   flow_t d= u == es[e= ns[u].pred].v ? es[e].up - es[e].flow : es[e].flow;
   if (delta > d) delta= d, u_out= u, side= 1;
  }
  for (u= v_in; u != lca; u= ns[u].par) {
   flow_t d= u == es[e= ns[u].pred].u ? es[e].up - es[e].flow : es[e].flow;
   if (delta >= d) delta= d, u_out= u, side= -1;
  }
  if (delta > 0) {
   es[in_arc].flow+= delta*= es[in_arc].state;
   for (u= es[in_arc].u; u != lca; u= ns[u].par) es[e].flow+= u == es[e= ns[u].pred].u ? -delta : delta;
   for (u= es[in_arc].v; u != lca; u= ns[u].par) es[e].flow+= u == es[e= ns[u].pred].u ? delta : -delta;
  }
  if (side == 0) return es[in_arc].state*= -1, void();
  int out_arc= ns[u_out].pred, p;
  es[in_arc].state= 0, es[out_arc].state= es[out_arc].flow ? -1 : 1;
  if (side == -1) std::swap(u_in, v_in);
  for (u= u_in; u != u_out; u= ns[u].par) bfs[S++]= u;
  assert(S <= n);
  for (i= S; i--;) ns[p= ns[u].par].par= u= bfs[i], ns[p].pred= ns[u].pred, link(prev[p], next[p]), link(prev[u + n + 1], p, u + n + 1);
  link(prev[u_in], next[u_in]), link(prev[v_in + n + 1], u_in, v_in + n + 1);
  ns[u_in].par= v_in, ns[u_in].pred= in_arc;
  cost_t pi_delta= u_in == es[in_arc].u ? -opp_cost(in_arc) : opp_cost(in_arc);
  for (i= 0, S= 1, bfs[0]= u_in; i < S; i++) {
   ns[u= bfs[i]].pi+= pi_delta;
   for (int v= next[u + n + 1]; v != u + n + 1; v= next[v]) bfs[S++]= v;
  }
 }
 void calc() {
  cost_t inf_cost= 1;
  for (int e= 0; e < m; e++) es[e].flow= 0, es[e].state= 1, es[e].up-= es[e].low, ns[es[e].u].sup-= es[e].low, ns[es[e].v].sup+= es[e].low, inf_cost+= std::abs(es[e].cost);
  ns[n]= {-1, -1, 0, 0}, es.resize(m + n), bfs.resize(n + 1);
  next.resize(2 * n + 2), std::iota(next.begin() + n + 1, next.end(), n + 1);
  prev.resize(2 * n + 2), std::iota(prev.begin() + n + 1, prev.end(), n + 1);
  for (int u= 0, e= m; u < n; u++, e++) {
   ns[u].par= n, ns[u].pred= e, link(prev[n + n + 1], u, n + n + 1);
   if (auto supply= ns[u].sup; supply >= 0) {
    ns[u].pi= -inf_cost;
    es[e]= {u, n, 0, supply, supply, inf_cost, 0};
   } else {
    ns[u].pi= inf_cost;
    es[e]= {n, u, 0, -supply, -supply, inf_cost, 0};
   }
  }
  int block_size= std::max(int(std::ceil(std::sqrt(m + n))), std::min(10, n + 1));
  for (int e= 0, in_arc, cnt, seen;; pivot(in_arc)) {
   cost_t minimum= 0;
   for (in_arc= -1, cnt= block_size, seen= m + n; seen--; e= e + 1 == m + n ? 0 : e + 1) {
    if (minimum > es[e].state * opp_cost(e)) minimum= es[e].state * opp_cost(e), in_arc= e;
    if (--cnt == 0 && minimum < 0) break;
    if (cnt == 0) cnt= block_size;
   }
   if (in_arc == -1) break;
  }
  for (int e= 0; e < m; e++) es[e].flow+= es[e].low, es[e].up+= es[e].low, ns[es[e].u].sup+= es[e].low, ns[es[e].v].sup-= es[e].low;
 }
public:
 NetworkSimplex(int n= 0): n(n), ns(n + 1) {}
 int add_vertex() { return ns.resize(n + 2), n++; }
 std::vector<int> add_vertices(const int size) {
  std::vector<int> ret(size);
  std::iota(ret.begin(), ret.end(), n);
  return ns.resize((n+= size) + 1), ret;
 }
 class EdgePtr {
  friend class NetworkSimplex;
  const NetworkSimplex *instance;
  int e;
  EdgePtr(const NetworkSimplex *const instance, const int e): instance(instance), e(e) {}
  const Edge &edge() const { return instance->es[e]; }
 public:
  EdgePtr()= default;
  int src() const { return edge().u; }
  int dst() const { return edge().v; }
  flow_t flow() const { return edge().flow; }
  flow_t lower() const { return edge().low; }
  flow_t upper() const { return edge().up; }
  cost_t cost() const { return edge().cost; }
  cost_t gain() const { return -edge().cost; }
 };
 EdgePtr add_edge(int u, int v, flow_t low, flow_t up, cost_t cost) {
  assert(0 <= u && u < n && 0 <= v && v < n);
  es.push_back({u, v, low, up, 0, obj * cost});
  return EdgePtr{this, m++};
 }
 void add_supply(int u, flow_t supply) { ns[u].sup= supply; }
 void add_demand(int u, flow_t demand) { ns[u].sup= -demand; }
 auto get_supply(int u) const { return ns[u].sup; }
 auto get_potential(int u) const { return ns[u].pi; }
 template <typename cost_sum_t= cost_t> auto get_result_value() const {
  cost_sum_t sum= 0;
  for (int e= 0; e < m; e++) {
   sum+= es[e].flow * cost_sum_t(es[e].cost);
  }
  return sum * obj;
 }
 bool b_flow() {
  flow_t sum_supply= 0;
  for (int u= 0; u < n; u++) sum_supply+= ns[u].sup;
  if (sum_supply != 0) return false;
  calc();
  for (int e= m; e < m + n; e++)
   if (es[e].flow != 0) return es.resize(m), false;
  return es.resize(m), true;
 }
};
#line 7 "test/yosupo/min_cost_b_flow.test.cpp"
using namespace std;
ostream &operator<<(ostream &stream, const __int128_t &v) {
 if (v == 0) stream << "0";
 __int128_t tmp;
 if (v < 0) stream << "-", tmp= -v;
 else tmp= v;
 std::string s;
 while (tmp) s+= '0' + (tmp % 10), tmp/= 10;
 return std::reverse(s.begin(), s.end()), stream << s;
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using MCF= NetworkSimplex<long long, long long>;
 int N, M;
 cin >> N >> M;
 MCF graph(N);
 vector<MCF::EdgePtr> edges;
 for (int i= 0; i < N; i++) {
  long long b;
  cin >> b;
  graph.add_supply(i, b);
 }
 for (int i= 0; i < M; i++) {
  long long s, t, l, u, c;
  cin >> s >> t >> l >> u >> c;
  edges.emplace_back(graph.add_edge(s, t, l, u, c));
 }
 if (graph.b_flow()) {
  cout << graph.get_result_value<__int128_t>() << '\n';
  for (int i= 0; i < N; i++) cout << graph.get_potential(i) << '\n';
  for (auto &e: edges) cout << e.flow() << '\n';
 } else {
  cout << "infeasible" << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	anti_ssp_00	AC	6 ms	4 MB
g++-13	empty_00	AC	4 ms	4 MB
g++-13	empty_01	AC	4 ms	4 MB
g++-13	empty_02	AC	4 ms	4 MB
g++-13	empty_03	AC	4 ms	4 MB
g++-13	example_00	AC	4 ms	4 MB
g++-13	example_01	AC	4 ms	4 MB
g++-13	example_02	AC	4 ms	4 MB
g++-13	goto_00	AC	5 ms	4 MB
g++-13	goto_01	AC	5 ms	4 MB
g++-13	goto_02	AC	5 ms	4 MB
g++-13	goto_03	AC	5 ms	4 MB
g++-13	goto_04	AC	5 ms	4 MB
g++-13	goto_05	AC	5 ms	4 MB
g++-13	goto_06	AC	5 ms	4 MB
g++-13	goto_07	AC	5 ms	4 MB
g++-13	goto_08	AC	5 ms	4 MB
g++-13	goto_09	AC	5 ms	4 MB
g++-13	handmade_00	AC	4 ms	4 MB
g++-13	handmade_01	AC	4 ms	4 MB
g++-13	handmade_02	AC	4 ms	4 MB
g++-13	handmade_03	AC	5 ms	4 MB
g++-13	large_random_00	AC	6 ms	4 MB
g++-13	large_random_01	AC	5 ms	4 MB
g++-13	large_random_02	AC	6 ms	4 MB
g++-13	large_random_03	AC	5 ms	4 MB
g++-13	large_random_04	AC	5 ms	4 MB
g++-13	large_random_05	AC	5 ms	4 MB
g++-13	large_random_06	AC	6 ms	4 MB
g++-13	large_random_07	AC	6 ms	4 MB
g++-13	large_random_08	AC	5 ms	4 MB
g++-13	large_random_09	AC	6 ms	4 MB
g++-13	near_maximum_00	AC	5 ms	4 MB
g++-13	near_minimum_00	AC	5 ms	4 MB
g++-13	small_random_00	AC	4 ms	4 MB
g++-13	small_random_01	AC	4 ms	4 MB
g++-13	small_random_02	AC	4 ms	4 MB
g++-13	small_random_03	AC	4 ms	4 MB
g++-13	small_random_04	AC	4 ms	4 MB
g++-13	small_random_05	AC	4 ms	4 MB
g++-13	small_random_06	AC	4 ms	4 MB
g++-13	small_random_07	AC	4 ms	4 MB
g++-13	small_random_08	AC	4 ms	4 MB
g++-13	small_random_09	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_00	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_01	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_02	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_03	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_04	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_05	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_06	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_07	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_08	AC	4 ms	4 MB
g++-13	small_random_possibly_infeasible_09	AC	4 ms	4 MB
clang++-18	anti_ssp_00	AC	5 ms	4 MB
clang++-18	empty_00	AC	4 ms	4 MB
clang++-18	empty_01	AC	4 ms	4 MB
clang++-18	empty_02	AC	4 ms	4 MB
clang++-18	empty_03	AC	4 ms	4 MB
clang++-18	example_00	AC	4 ms	4 MB
clang++-18	example_01	AC	4 ms	4 MB
clang++-18	example_02	AC	4 ms	4 MB
clang++-18	goto_00	AC	5 ms	4 MB
clang++-18	goto_01	AC	5 ms	4 MB
clang++-18	goto_02	AC	5 ms	4 MB
clang++-18	goto_03	AC	5 ms	4 MB
clang++-18	goto_04	AC	5 ms	4 MB
clang++-18	goto_05	AC	5 ms	4 MB
clang++-18	goto_06	AC	5 ms	4 MB
clang++-18	goto_07	AC	5 ms	4 MB
clang++-18	goto_08	AC	5 ms	4 MB
clang++-18	goto_09	AC	5 ms	4 MB
clang++-18	handmade_00	AC	4 ms	4 MB
clang++-18	handmade_01	AC	4 ms	4 MB
clang++-18	handmade_02	AC	4 ms	4 MB
clang++-18	handmade_03	AC	5 ms	4 MB
clang++-18	large_random_00	AC	5 ms	4 MB
clang++-18	large_random_01	AC	5 ms	4 MB
clang++-18	large_random_02	AC	6 ms	4 MB
clang++-18	large_random_03	AC	5 ms	4 MB
clang++-18	large_random_04	AC	5 ms	4 MB
clang++-18	large_random_05	AC	5 ms	4 MB
clang++-18	large_random_06	AC	6 ms	4 MB
clang++-18	large_random_07	AC	5 ms	4 MB
clang++-18	large_random_08	AC	5 ms	4 MB
clang++-18	large_random_09	AC	5 ms	4 MB
clang++-18	near_maximum_00	AC	5 ms	4 MB
clang++-18	near_minimum_00	AC	5 ms	4 MB
clang++-18	small_random_00	AC	4 ms	4 MB
clang++-18	small_random_01	AC	4 ms	4 MB
clang++-18	small_random_02	AC	4 ms	4 MB
clang++-18	small_random_03	AC	4 ms	4 MB
clang++-18	small_random_04	AC	4 ms	4 MB
clang++-18	small_random_05	AC	4 ms	4 MB
clang++-18	small_random_06	AC	4 ms	4 MB
clang++-18	small_random_07	AC	4 ms	4 MB
clang++-18	small_random_08	AC	4 ms	4 MB
clang++-18	small_random_09	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_00	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_01	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_02	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_03	AC	5 ms	4 MB
clang++-18	small_random_possibly_infeasible_04	AC	5 ms	4 MB
clang++-18	small_random_possibly_infeasible_05	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_06	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_07	AC	4 ms	4 MB
clang++-18	small_random_possibly_infeasible_08	AC	5 ms	4 MB
clang++-18	small_random_possibly_infeasible_09	AC	4 ms	4 MB

Back to top page