firiexp's Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/yosupo_min_cost_b_flow.test.cpp
- View this file on GitHub
- Last update: 2026-03-22 13:47:31+09:00
- Problem: https://judge.yosupo.jp/problem/min_cost_b_flow
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/min_cost_b_flow"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include "../util/fastio.cpp"
#include "../graph/minimum_cost_b_flow.cpp"
void write_i128(Printer& pr, __int128_t x) {
if(x == 0) {
pr.print('0');
return;
}
if(x < 0) {
pr.print('-');
x = -x;
}
string s;
while(x > 0) {
s.push_back(char('0' + x % 10));
x /= 10;
}
reverse(s.begin(), s.end());
pr.print(s);
}
int main() {
Scanner sc;
Printer pr;
int n, m;
sc.read(n, m);
MinimumCostBFlow<ll, ll> mcf(n);
for (int i = 0; i < n; ++i) {
ll b;
sc.read(b);
mcf.add_supply(i, b);
}
for (int i = 0; i < m; ++i) {
int s, t;
ll lower, upper, cost;
sc.read(s, t, lower, upper, cost);
mcf.add_edge(s, t, lower, upper, cost);
}
auto [ok, cost] = mcf.solve();
if(!ok) {
pr.println("infeasible");
return 0;
}
write_i128(pr, cost);
pr.println();
auto potential = mcf.get_potential();
for (int i = 0; i < n; ++i) {
pr.print(potential[i]);
pr.print(i + 1 == n ? '\n' : ' ');
}
auto flow = mcf.get_flows();
for (int i = 0; i < m; ++i) {
pr.println(flow[i]);
}
return 0;
}#line 1 "test/yosupo_min_cost_b_flow.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/min_cost_b_flow"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#line 10 "test/yosupo_min_cost_b_flow.test.cpp"
#include <type_traits>
#line 1 "util/fastio.cpp"
using namespace std;
extern "C" int fileno(FILE *);
extern "C" int isatty(int);
template<class T, class = void>
struct is_fastio_range : false_type {};
template<class T>
struct is_fastio_range<T, void_t<decltype(declval<T &>().begin()), decltype(declval<T &>().end())>> : true_type {};
template<class T, class = void>
struct has_fastio_value : false_type {};
template<class T>
struct has_fastio_value<T, void_t<decltype(declval<const T &>().value())>> : true_type {};
struct FastIoDigitTable {
char num[40000];
constexpr FastIoDigitTable() : num() {
for (int i = 0; i < 10000; ++i) {
int x = i;
for (int j = 3; j >= 0; --j) {
num[i * 4 + j] = char('0' + x % 10);
x /= 10;
}
}
}
};
struct Scanner {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE + 1];
int idx, size;
bool interactive;
Scanner() : idx(0), size(0), interactive(isatty(fileno(stdin))) {}
inline void load() {
int len = size - idx;
memmove(buf, buf + idx, len);
if (interactive) {
if (fgets(buf + len, BUFSIZE + 1 - len, stdin)) size = len + (int)strlen(buf + len);
else size = len;
} else {
size = len + (int)fread(buf + len, 1, BUFSIZE - len, stdin);
}
idx = 0;
buf[size] = 0;
}
inline void ensure() {
if (idx + OFFSET > size) load();
}
inline void ensure_interactive() {
if (idx == size) load();
}
inline char skip() {
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
return buf[idx++];
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
return buf[idx++];
}
template<class T, typename enable_if<is_integral<T>::value, int>::type = 0>
void read(T &x) {
if (interactive) {
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
ensure_interactive();
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
ensure_interactive();
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
return;
}
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void read(T &x) {
long long v;
read(v);
x = T(v);
}
template<class Head, class Next, class... Tail>
void read(Head &head, Next &next, Tail &...tail) {
read(head);
read(next, tail...);
}
template<class T, class U>
void read(pair<T, U> &p) {
read(p.first, p.second);
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void read(T &a) {
for (auto &x : a) read(x);
}
void read(char &c) {
c = skip();
}
void read(string &s) {
s.clear();
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
if (size == 0) break;
}
if (idx < size) ++idx;
return;
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
}
if (idx < size) ++idx;
}
};
struct Printer {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE];
int idx;
bool interactive;
inline static constexpr FastIoDigitTable table{};
Printer() : idx(0), interactive(isatty(fileno(stdout))) {}
~Printer() { flush(); }
inline void flush() {
if (idx) {
fwrite(buf, 1, idx, stdout);
idx = 0;
}
}
inline void pc(char c) {
if (idx > BUFSIZE - OFFSET) flush();
buf[idx++] = c;
if (interactive && c == '\n') flush();
}
inline void print_range(const char *s, size_t n) {
size_t pos = 0;
while (pos < n) {
if (idx == BUFSIZE) flush();
size_t chunk = min(n - pos, (size_t)(BUFSIZE - idx));
memcpy(buf + idx, s + pos, chunk);
idx += (int)chunk;
pos += chunk;
}
}
void print(const char *s) {
print_range(s, strlen(s));
}
void print(const string &s) {
print_range(s.data(), s.size());
}
void print(char c) {
pc(c);
}
void print(bool b) {
pc(char('0' + (b ? 1 : 0)));
}
template<class T, typename enable_if<is_integral<T>::value && !is_same<T, bool>::value, int>::type = 0>
void print(T x) {
if (idx > BUFSIZE - 100) flush();
using U = typename make_unsigned<T>::type;
U y;
if constexpr (is_signed<T>::value) {
if (x < 0) {
buf[idx++] = '-';
y = U(0) - static_cast<U>(x);
} else {
y = static_cast<U>(x);
}
} else {
y = x;
}
if (y == 0) {
buf[idx++] = '0';
return;
}
static constexpr int TMP_SIZE = sizeof(U) * 10 / 4;
char tmp[TMP_SIZE];
int pos = TMP_SIZE;
while (y >= 10000) {
pos -= 4;
memcpy(tmp + pos, table.num + (y % 10000) * 4, 4);
y /= 10000;
}
if (y >= 1000) {
memcpy(buf + idx, table.num + (y << 2), 4);
idx += 4;
} else if (y >= 100) {
memcpy(buf + idx, table.num + (y << 2) + 1, 3);
idx += 3;
} else if (y >= 10) {
unsigned q = (unsigned(y) * 205) >> 11;
buf[idx] = char('0' + q);
buf[idx + 1] = char('0' + (unsigned(y) - q * 10));
idx += 2;
} else {
buf[idx++] = char('0' + y);
}
memcpy(buf + idx, tmp + pos, TMP_SIZE - pos);
idx += TMP_SIZE - pos;
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void print(const T &x) {
print(x.value());
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void print(const T &a) {
bool first = true;
for (auto &&x : a) {
if (!first) pc(' ');
first = false;
print(x);
}
}
template<class T>
void println(const T &x) {
print(x);
pc('\n');
}
template<class Head, class... Tail>
void println(const Head &head, const Tail &...tail) {
print(head);
((pc(' '), print(tail)), ...);
pc('\n');
}
void println() {
pc('\n');
}
};
template<class T>
Scanner &operator>>(Scanner &in, T &x) {
in.read(x);
return in;
}
template<class T>
Printer &operator<<(Printer &out, const T &x) {
out.print(x);
return out;
}
/**
* @brief 高速入出力(Fast IO)
*/
#line 1 "graph/minimum_cost_b_flow.cpp"
template<class Flow, class Cost>
struct MinimumCostBFlow {
using Sum = __int128_t;
struct Edge {
int from, to, rev;
Flow flow, cap;
Cost cost;
Flow residual_cap() const {
return cap - flow;
}
};
struct EdgeRef {
int from, idx;
};
int n;
vector<vector<Edge>> g;
vector<Flow> b;
vector<EdgeRef> edges;
vector<Cost> potential;
explicit MinimumCostBFlow(int n) : n(n), g(n), b(n, 0), potential(n, 0) {}
void add_supply(int v, Flow x) {
b[v] += x;
}
void add_demand(int v, Flow x) {
b[v] -= x;
}
int add_edge(int from, int to, Flow lower, Flow upper, Cost cost) {
assert(lower <= upper);
int idx = (int)g[from].size();
int rev = from == to ? idx + 1 : (int)g[to].size();
g[from].push_back({from, to, rev, 0, upper, cost});
g[to].push_back({to, from, idx, 0, -lower, -cost});
edges.push_back({from, idx});
return (int)edges.size() - 1;
}
Edge& rev_edge(const Edge& e) {
return g[e.to][e.rev];
}
const Edge& get_edge(int i) const {
return g[edges[i].from][edges[i].idx];
}
vector<Flow> get_flows() const {
vector<Flow> ret(edges.size());
for (int i = 0; i < (int)edges.size(); ++i) ret[i] = get_edge(i).flow;
return ret;
}
vector<Cost> get_potential() const {
vector<Cost> ret(n, 0);
for (int iter = 0; iter < n; ++iter) {
bool updated = false;
for (int v = 0; v < n; ++v) {
for (auto&& e : g[v]) {
if(e.residual_cap() <= 0) continue;
if(ret[e.to] > ret[e.from] + e.cost) {
ret[e.to] = ret[e.from] + e.cost;
updated = true;
}
}
}
if(!updated) break;
}
return ret;
}
pair<bool, Sum> solve() {
const Cost unreachable = numeric_limits<Cost>::max();
vector<Cost> dist(n);
vector<Edge*> parent(n);
vector<int> excess, deficit;
priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<pair<Cost, int>>> pq;
Cost farthest = 0;
auto push = [&](Edge& e, Flow amount) {
e.flow += amount;
rev_edge(e).flow -= amount;
};
auto residual_cost = [&](const Edge& e) {
return e.cost + potential[e.from] - potential[e.to];
};
auto saturate_negative = [&](Flow delta) {
excess.clear();
deficit.clear();
for (auto&& es : g) {
for (auto&& e : es) {
Flow rcap = e.residual_cap();
if(rcap < delta) continue;
if(residual_cost(e) < 0) {
push(e, rcap);
b[e.from] -= rcap;
b[e.to] += rcap;
}
}
}
for (int v = 0; v < n; ++v) {
if(b[v] > 0) excess.push_back(v);
if(b[v] < 0) deficit.push_back(v);
}
};
auto dual = [&](Flow delta) {
fill(dist.begin(), dist.end(), unreachable);
fill(parent.begin(), parent.end(), nullptr);
excess.erase(remove_if(excess.begin(), excess.end(), [&](int v) {
return b[v] < delta;
}), excess.end());
deficit.erase(remove_if(deficit.begin(), deficit.end(), [&](int v) {
return b[v] > -delta;
}), deficit.end());
while(!pq.empty()) pq.pop();
for (int v : excess) {
dist[v] = 0;
pq.emplace(0, v);
}
farthest = 0;
int reached = 0;
while(!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if(dist[v] != d) continue;
farthest = d;
if(b[v] <= -delta) ++reached;
if(reached >= (int)deficit.size()) break;
for (auto&& e : g[v]) {
if(e.residual_cap() < delta) continue;
Cost nd = d + residual_cost(e);
if(nd >= dist[e.to]) continue;
dist[e.to] = nd;
parent[e.to] = &e;
pq.emplace(nd, e.to);
}
}
for (int v = 0; v < n; ++v) {
potential[v] += min(dist[v], farthest);
}
return reached > 0;
};
auto primal = [&](Flow delta) {
for (int t : deficit) {
if(dist[t] > farthest) continue;
Flow f = -b[t];
int v = t;
while(parent[v] != nullptr && f >= delta) {
f = min(f, parent[v]->residual_cap());
v = parent[v]->from;
}
f = min(f, b[v]);
if(f < delta) continue;
v = t;
while(parent[v] != nullptr) {
Edge& e = *parent[v];
push(e, f);
int u = e.from;
parent[v] = nullptr;
v = u;
}
b[t] += f;
b[v] -= f;
}
};
for (auto&& es : g) {
for (auto&& e : es) {
Flow rcap = e.residual_cap();
if(rcap < 0) {
push(e, rcap);
b[e.from] -= rcap;
b[e.to] += rcap;
}
}
}
Flow max_cap = 1;
for (auto&& es : g) {
for (auto&& e : es) {
max_cap = max(max_cap, e.residual_cap());
}
}
Flow delta = 1;
while(delta <= max_cap / 2) delta <<= 1;
for (delta >>= 1; delta > 0; delta >>= 1) {
saturate_negative(delta);
while(dual(delta)) primal(delta);
}
Sum value = 0;
bool ok = true;
for (int v = 0; v < n; ++v) {
if(b[v] != 0) ok = false;
}
for (int i = 0; i < (int)edges.size(); ++i) {
auto&& e = get_edge(i);
value += (Sum)e.flow * (Sum)e.cost;
}
return {ok, value};
}
};
/**
* @brief 最小費用b-flow(Min-Cost b-Flow)
*/
#line 14 "test/yosupo_min_cost_b_flow.test.cpp"
void write_i128(Printer& pr, __int128_t x) {
if(x == 0) {
pr.print('0');
return;
}
if(x < 0) {
pr.print('-');
x = -x;
}
string s;
while(x > 0) {
s.push_back(char('0' + x % 10));
x /= 10;
}
reverse(s.begin(), s.end());
pr.print(s);
}
int main() {
Scanner sc;
Printer pr;
int n, m;
sc.read(n, m);
MinimumCostBFlow<ll, ll> mcf(n);
for (int i = 0; i < n; ++i) {
ll b;
sc.read(b);
mcf.add_supply(i, b);
}
for (int i = 0; i < m; ++i) {
int s, t;
ll lower, upper, cost;
sc.read(s, t, lower, upper, cost);
mcf.add_edge(s, t, lower, upper, cost);
}
auto [ok, cost] = mcf.solve();
if(!ok) {
pr.println("infeasible");
return 0;
}
write_i128(pr, cost);
pr.println();
auto potential = mcf.get_potential();
for (int i = 0; i < n; ++i) {
pr.print(potential[i]);
pr.print(i + 1 == n ? '\n' : ' ');
}
auto flow = mcf.get_flows();
for (int i = 0; i < m; ++i) {
pr.println(flow[i]);
}
return 0;
}