min_cost_b_flow.hpp¶
处理点供需、边流量上下界与费用的最小/最大费用可行流，并判断是否无解。
Complexity: Time: O(E log U (E + V log V)), where U is the largest absolute capacity or balance. Space: O(V + E).
AC 记录：min_cost_b_flow。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(E log U (E + V log V)), where U is the largest
/// absolute capacity or balance. Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
/// @brief Minimum- or maximum-cost feasible b-flow with lower and upper bounds.
/// Lower bounds are represented as reverse residual capacity and vertex
/// supplies are maintained as excesses. Capacity scaling repeatedly saturates
/// negative reduced-cost residual edges, then a multi-source Dijkstra dual
/// step updates potentials and a primal step routes one scaling unit from
/// excess vertices to deficits. When the scale reaches one, residual reduced
/// costs certify optimality; a remaining excess certifies infeasibility.
enum Objective {
MINIMIZE = 1,
MAXIMIZE = -1,
};
enum class Status {
OPTIMAL,
INFEASIBLE,
};
template <class Flow, class Cost, Objective objective = Objective::MINIMIZE,
Flow SCALING_FACTOR = 2>
class MinCostFlow {
using V_id = uint32_t;
using E_id = uint32_t;
class Edge {
friend class MinCostFlow;
V_id src, dst;
Flow flw, cap;
Cost cst;
E_id rev;
public:
Edge() = default;
Edge(const V_id src, const V_id dst, const Flow cap, const Cost cst,
const E_id rev)
: src(src), dst(dst), flw(0), cap(cap), cst(cst), rev(rev) {}
[[nodiscard]] Flow residual_cap() const { return cap - flw; }
};
public:
class EdgePtr {
friend class MinCostFlow;
const MinCostFlow *obj;
V_id v;
E_id e;
EdgePtr(const MinCostFlow *const obj, const V_id v, const E_id e)
: obj(obj), v(v), e(e) {}
[[nodiscard]] const Edge &edge() const { return obj->g[v][e]; }
[[nodiscard]] const Edge &rev() const {
const Edge &e = edge();
return obj->g[e.dst][e.rev];
}
public:
EdgePtr() = default;
[[nodiscard]] V_id src() const { return v; }
[[nodiscard]] V_id dst() const { return edge().dst; }
[[nodiscard]] Flow flow() const { return edge().flw; }
[[nodiscard]] Flow lower() const { return -rev().cap; }
[[nodiscard]] Flow upper() const { return edge().cap; }
[[nodiscard]] Cost cost() const { return edge().cst; }
[[nodiscard]] Cost gain() const { return -edge().cst; }
};
private:
V_id n;
std::vector<std::vector<Edge>> g;
std::vector<Flow> b;
public:
MinCostFlow() : n(0) {}
V_id add_vertex() {
++n;
g.resize(n);
b.resize(n);
return n - 1;
}
std::vector<V_id> add_vertices(const size_t siz) {
std::vector<V_id> ret(siz);
std::iota(std::begin(ret), std::end(ret), n);
n += siz;
g.resize(n);
b.resize(n);
return ret;
}
EdgePtr add_edge(const V_id src, const V_id dst, const Flow lo, const Flow hi,
const Cost cst) {
const E_id e = g[src].size(), re = src == dst ? e + 1 : g[dst].size();
assert(lo <= hi);
g[src].emplace_back(Edge{src, dst, hi, cst * objective, re});
g[dst].emplace_back(Edge{dst, src, -lo, -cst * objective, e});
return EdgePtr{this, src, e};
}
void add_supply(const V_id v, const Flow amt) { b[v] += amt; }
void add_demand(const V_id v, const Flow amt) { b[v] -= amt; }
private:
// Variables used in calculation
const Cost inf = std::numeric_limits<Cost>::max();
Cost far;
std::vector<Cost> pot;
std::vector<Cost> dis;
std::vector<Edge *> fa; // out-forrest.
std::priority_queue<std::pair<Cost, int>, std::vector<std::pair<Cost, int>>,
std::greater<>>
pq; // should be empty outside of dual()
std::vector<V_id> ev, dv;
Edge &rev(const Edge &e) { return g[e.dst][e.rev]; }
void push(Edge &e, const Flow amt) {
e.flw += amt;
g[e.dst][e.rev].flw -= amt;
}
Cost residual_cost(const V_id src, const V_id dst, const Edge &e) {
return e.cst + pot[src] - pot[dst];
}
bool dual(const Flow dlt) {
dis.assign(n, inf);
fa.assign(n, nullptr);
ev.erase(std::remove_if(std::begin(ev), std::end(ev),
[&](const V_id v) { return b[v] < dlt; }),
std::end(ev));
dv.erase(std::remove_if(std::begin(dv), std::end(dv),
[&](const V_id v) { return b[v] > -dlt; }),
std::end(dv));
for (const auto v : ev)
pq.emplace(dis[v] = 0, v);
far = 0;
std::size_t nd = 0;
while (!pq.empty()) {
Cost d;
std::size_t u;
std::tie(d, u) = pq.top();
// const auto [d, u] = pq.top();
pq.pop();
if (dis[u] < d)
continue;
far = d;
if (b[u] <= -dlt)
++nd;
if (nd >= dv.size())
break;
for (auto &e : g[u]) {
if (e.residual_cap() < dlt)
continue;
const auto v = e.dst;
const auto vtx = d + residual_cost(u, v, e);
if (vtx >= dis[v])
continue;
pq.emplace(dis[v] = vtx, v);
fa[v] = &e;
}
}
pq = decltype(pq)(); // pq.clear() doesn't exist.
for (V_id v = 0; v < n; ++v) {
pot[v] += std::min(dis[v], far);
}
return nd > 0;
}
void primal(const Flow dlt) {
for (const auto t : dv) {
if (dis[t] > far)
continue;
Flow f = -b[t];
V_id v;
for (v = t; fa[v] != nullptr; v = fa[v]->src) {
f = std::min(f, fa[v]->residual_cap());
}
f = std::min(f, b[v]);
f -= f % dlt;
if (f <= 0)
continue;
for (v = t; fa[v] != nullptr;) {
auto &e = *fa[v];
push(e, f);
int u = fa[v]->src;
if (e.residual_cap() <= 0)
fa[v] = nullptr;
v = u;
}
b[t] += f;
b[v] -= f;
}
}
void saturate_negative(const Flow dlt) {
ev.clear();
dv.clear();
for (auto &es : g)
for (auto &e : es) {
Flow ca1 = e.residual_cap();
ca1 -= ca1 % dlt;
const Cost cs1 = residual_cost(e.src, e.dst, e);
if (cs1 < 0 || ca1 < 0) {
push(e, ca1);
b[e.src] -= ca1;
b[e.dst] += ca1;
}
}
for (V_id v = 0; v < n; ++v)
if (b[v] != 0) {
(b[v] > 0 ? ev : dv).emplace_back(v);
}
}
public:
std::pair<Status, Cost> solve() {
pot.resize(n);
Flow in1 = 1;
for (const auto t : b)
in1 = std::max({in1, t, -t});
for (const auto &es : g)
for (const auto &e : es)
in1 = std::max({in1, e.residual_cap(), -e.residual_cap()});
Flow dlt = 1;
while (dlt < in1)
dlt *= SCALING_FACTOR;
for (; dlt; dlt /= SCALING_FACTOR) {
saturate_negative(dlt);
while (dual(dlt))
primal(dlt);
}
Cost val = 0;
for (const auto &es : g)
for (const auto &e : es) {
val += e.flw * e.cst;
}
val /= 2;
if (ev.empty() && dv.empty()) {
return {Status::OPTIMAL, val / objective};
} else {
return {Status::INFEASIBLE, val / objective};
}
}
std::vector<Cost> get_potential() {
// Not strictly necessary, but re-calculate pot to bound the pot values,
// plus make them somewhat canonical so that it is robust for the algorithm chaneges.
std::fill(std::begin(pot), std::end(pot), 0);
for (size_t i = 0; i < n; ++i)
for (const auto &es : g)
for (const auto &e : es)
if (e.residual_cap() > 0)
pot[e.dst] = std::min(pot[e.dst], pot[e.src] + e.cst);
return pot;
}
template <class T> T get_result_value() {
T val = 0;
for (const auto &es : g)
for (const auto &e : es) {
val += (T)(e.flw) * (T)(e.cst);
}
val /= (T)2;
return val;
}
std::vector<size_t> get_cut() {
std::vector<size_t> res;
if (ev.empty())
return res;
for (size_t v = 0; v < n; ++v) {
if (dv.empty() || (dis[v] < inf))
res.emplace_back(v);
}
return res;
}
};
} // namespace noya
#ifndef NOYA_MIN_COST_B_FLOW_HPP
#define NOYA_MIN_COST_B_FLOW_HPP 1
/// @complexity Time: O(E log U (E + V log V)), where U is the largest
/// absolute capacity or balance. Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
/// @brief Minimum- or maximum-cost feasible b-flow with lower and upper bounds.
/// Lower bounds are represented as reverse residual capacity and vertex
/// supplies are maintained as excesses. Capacity scaling repeatedly saturates
/// negative reduced-cost residual edges, then a multi-source Dijkstra dual
/// step updates potentials and a primal step routes one scaling unit from
/// excess vertices to deficits. When the scale reaches one, residual reduced
/// costs certify optimality; a remaining excess certifies infeasibility.
enum Objective {
MINIMIZE = 1,
MAXIMIZE = -1,
};
enum class Status {
OPTIMAL,
INFEASIBLE,
};
template <class Flow, class Cost, Objective objective = Objective::MINIMIZE,
Flow SCALING_FACTOR = 2>
class MinCostFlow {
using V_id = uint32_t;
using E_id = uint32_t;
class Edge {
friend class MinCostFlow;
V_id src, dst;
Flow flw, cap;
Cost cst;
E_id rev;
public:
Edge() = default;
Edge(const V_id src, const V_id dst, const Flow cap, const Cost cst,
const E_id rev)
: src(src), dst(dst), flw(0), cap(cap), cst(cst), rev(rev) {}
[[nodiscard]] Flow residual_cap() const { return cap - flw; }
};
public:
class EdgePtr {
friend class MinCostFlow;
const MinCostFlow *obj;
V_id v;
E_id e;
EdgePtr(const MinCostFlow *const obj, const V_id v, const E_id e)
: obj(obj), v(v), e(e) {}
[[nodiscard]] const Edge &edge() const { return obj->g[v][e]; }
[[nodiscard]] const Edge &rev() const {
const Edge &e = edge();
return obj->g[e.dst][e.rev];
}
public:
EdgePtr() = default;
[[nodiscard]] V_id src() const { return v; }
[[nodiscard]] V_id dst() const { return edge().dst; }
[[nodiscard]] Flow flow() const { return edge().flw; }
[[nodiscard]] Flow lower() const { return -rev().cap; }
[[nodiscard]] Flow upper() const { return edge().cap; }
[[nodiscard]] Cost cost() const { return edge().cst; }
[[nodiscard]] Cost gain() const { return -edge().cst; }
};
private:
V_id n;
std::vector<std::vector<Edge>> g;
std::vector<Flow> b;
public:
MinCostFlow() : n(0) {}
V_id add_vertex() {
++n;
g.resize(n);
b.resize(n);
return n - 1;
}
std::vector<V_id> add_vertices(const size_t siz) {
std::vector<V_id> ret(siz);
std::iota(std::begin(ret), std::end(ret), n);
n += siz;
g.resize(n);
b.resize(n);
return ret;
}
EdgePtr add_edge(const V_id src, const V_id dst, const Flow lo, const Flow hi,
const Cost cst) {
const E_id e = g[src].size(), re = src == dst ? e + 1 : g[dst].size();
assert(lo <= hi);
g[src].emplace_back(Edge{src, dst, hi, cst * objective, re});
g[dst].emplace_back(Edge{dst, src, -lo, -cst * objective, e});
return EdgePtr{this, src, e};
}
void add_supply(const V_id v, const Flow amt) { b[v] += amt; }
void add_demand(const V_id v, const Flow amt) { b[v] -= amt; }
private:
// Variables used in calculation
const Cost inf = std::numeric_limits<Cost>::max();
Cost far;
std::vector<Cost> pot;
std::vector<Cost> dis;
std::vector<Edge *> fa; // out-forrest.
std::priority_queue<std::pair<Cost, int>, std::vector<std::pair<Cost, int>>,
std::greater<>>
pq; // should be empty outside of dual()
std::vector<V_id> ev, dv;
Edge &rev(const Edge &e) { return g[e.dst][e.rev]; }
void push(Edge &e, const Flow amt) {
e.flw += amt;
g[e.dst][e.rev].flw -= amt;
}
Cost residual_cost(const V_id src, const V_id dst, const Edge &e) {
return e.cst + pot[src] - pot[dst];
}
bool dual(const Flow dlt) {
dis.assign(n, inf);
fa.assign(n, nullptr);
ev.erase(std::remove_if(std::begin(ev), std::end(ev),
[&](const V_id v) { return b[v] < dlt; }),
std::end(ev));
dv.erase(std::remove_if(std::begin(dv), std::end(dv),
[&](const V_id v) { return b[v] > -dlt; }),
std::end(dv));
for (const auto v : ev)
pq.emplace(dis[v] = 0, v);
far = 0;
std::size_t nd = 0;
while (!pq.empty()) {
Cost d;
std::size_t u;
std::tie(d, u) = pq.top();
// const auto [d, u] = pq.top();
pq.pop();
if (dis[u] < d)
continue;
far = d;
if (b[u] <= -dlt)
++nd;
if (nd >= dv.size())
break;
for (auto &e : g[u]) {
if (e.residual_cap() < dlt)
continue;
const auto v = e.dst;
const auto vtx = d + residual_cost(u, v, e);
if (vtx >= dis[v])
continue;
pq.emplace(dis[v] = vtx, v);
fa[v] = &e;
}
}
pq = decltype(pq)(); // pq.clear() doesn't exist.
for (V_id v = 0; v < n; ++v) {
pot[v] += std::min(dis[v], far);
}
return nd > 0;
}
void primal(const Flow dlt) {
for (const auto t : dv) {
if (dis[t] > far)
continue;
Flow f = -b[t];
V_id v;
for (v = t; fa[v] != nullptr; v = fa[v]->src) {
f = std::min(f, fa[v]->residual_cap());
}
f = std::min(f, b[v]);
f -= f % dlt;
if (f <= 0)
continue;
for (v = t; fa[v] != nullptr;) {
auto &e = *fa[v];
push(e, f);
int u = fa[v]->src;
if (e.residual_cap() <= 0)
fa[v] = nullptr;
v = u;
}
b[t] += f;
b[v] -= f;
}
}
void saturate_negative(const Flow dlt) {
ev.clear();
dv.clear();
for (auto &es : g)
for (auto &e : es) {
Flow ca1 = e.residual_cap();
ca1 -= ca1 % dlt;
const Cost cs1 = residual_cost(e.src, e.dst, e);
if (cs1 < 0 || ca1 < 0) {
push(e, ca1);
b[e.src] -= ca1;
b[e.dst] += ca1;
}
}
for (V_id v = 0; v < n; ++v)
if (b[v] != 0) {
(b[v] > 0 ? ev : dv).emplace_back(v);
}
}
public:
std::pair<Status, Cost> solve() {
pot.resize(n);
Flow in1 = 1;
for (const auto t : b)
in1 = std::max({in1, t, -t});
for (const auto &es : g)
for (const auto &e : es)
in1 = std::max({in1, e.residual_cap(), -e.residual_cap()});
Flow dlt = 1;
while (dlt < in1)
dlt *= SCALING_FACTOR;
for (; dlt; dlt /= SCALING_FACTOR) {
saturate_negative(dlt);
while (dual(dlt))
primal(dlt);
}
Cost val = 0;
for (const auto &es : g)
for (const auto &e : es) {
val += e.flw * e.cst;
}
val /= 2;
if (ev.empty() && dv.empty()) {
return {Status::OPTIMAL, val / objective};
} else {
return {Status::INFEASIBLE, val / objective};
}
}
std::vector<Cost> get_potential() {
// Not strictly necessary, but re-calculate pot to bound the pot values,
// plus make them somewhat canonical so that it is robust for the algorithm chaneges.
std::fill(std::begin(pot), std::end(pot), 0);
for (size_t i = 0; i < n; ++i)
for (const auto &es : g)
for (const auto &e : es)
if (e.residual_cap() > 0)
pot[e.dst] = std::min(pot[e.dst], pot[e.src] + e.cst);
return pot;
}
template <class T> T get_result_value() {
T val = 0;
for (const auto &es : g)
for (const auto &e : es) {
val += (T)(e.flw) * (T)(e.cst);
}
val /= (T)2;
return val;
}
std::vector<size_t> get_cut() {
std::vector<size_t> res;
if (ev.empty())
return res;
for (size_t v = 0; v < n; ++v) {
if (dv.empty() || (dis[v] < inf))
res.emplace_back(v);
}
return res;
}
};
} // namespace noya
#endif // NOYA_MIN_COST_B_FLOW_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O(E log U (E + V log V)), where U is the largest
/// absolute capacity or balance. Space: O(V + E).
namespace noya {
/// @brief Minimum- or maximum-cost feasible b-flow with lower and upper bounds.
/// Lower bounds are represented as reverse residual capacity and vertex
/// supplies are maintained as excesses. Capacity scaling repeatedly saturates
/// negative reduced-cost residual edges, then a multi-source Dijkstra dual
/// step updates potentials and a primal step routes one scaling unit from
/// excess vertices to deficits. When the scale reaches one, residual reduced
/// costs certify optimality; a remaining excess certifies infeasibility.
enum Objective {
MINIMIZE = 1,
MAXIMIZE = -1,
};
enum class Status {
OPTIMAL,
INFEASIBLE,
};
template <class Flow, class Cost, Objective objective = Objective::MINIMIZE,
Flow SCALING_FACTOR = 2>
class MinCostFlow {
using V_id = uint32_t;
using E_id = uint32_t;
class Edge {
friend class MinCostFlow;
V_id src, dst;
Flow flw, cap;
Cost cst;
E_id rev;
public:
Edge() = default;
Edge(const V_id src, const V_id dst, const Flow cap, const Cost cst,
const E_id rev)
: src(src), dst(dst), flw(0), cap(cap), cst(cst), rev(rev) {}
[[nodiscard]] Flow residual_cap() const { return cap - flw; }
};
public:
class EdgePtr {
friend class MinCostFlow;
const MinCostFlow *obj;
V_id v;
E_id e;
EdgePtr(const MinCostFlow *const obj, const V_id v, const E_id e)
: obj(obj), v(v), e(e) {}
[[nodiscard]] const Edge &edge() const { return obj->g[v][e]; }
[[nodiscard]] const Edge &rev() const {
const Edge &e = edge();
return obj->g[e.dst][e.rev];
}
public:
EdgePtr() = default;
[[nodiscard]] V_id src() const { return v; }
[[nodiscard]] V_id dst() const { return edge().dst; }
[[nodiscard]] Flow flow() const { return edge().flw; }
[[nodiscard]] Flow lower() const { return -rev().cap; }
[[nodiscard]] Flow upper() const { return edge().cap; }
[[nodiscard]] Cost cost() const { return edge().cst; }
[[nodiscard]] Cost gain() const { return -edge().cst; }
};
private:
V_id n;
std::vector<std::vector<Edge>> g;
std::vector<Flow> b;
public:
MinCostFlow() : n(0) {}
V_id add_vertex() {
++n;
g.resize(n);
b.resize(n);
return n - 1;
}
std::vector<V_id> add_vertices(const size_t siz) {
std::vector<V_id> ret(siz);
std::iota(std::begin(ret), std::end(ret), n);
n += siz;
g.resize(n);
b.resize(n);
return ret;
}
EdgePtr add_edge(const V_id src, const V_id dst, const Flow lo, const Flow hi,
const Cost cst) {
const E_id e = g[src].size(), re = src == dst ? e + 1 : g[dst].size();
assert(lo <= hi);
g[src].emplace_back(Edge{src, dst, hi, cst * objective, re});
g[dst].emplace_back(Edge{dst, src, -lo, -cst * objective, e});
return EdgePtr{this, src, e};
}
void add_supply(const V_id v, const Flow amt) { b[v] += amt; }
void add_demand(const V_id v, const Flow amt) { b[v] -= amt; }
private:
// Variables used in calculation
const Cost inf = std::numeric_limits<Cost>::max();
Cost far;
std::vector<Cost> pot;
std::vector<Cost> dis;
std::vector<Edge *> fa; // out-forrest.
std::priority_queue<std::pair<Cost, int>, std::vector<std::pair<Cost, int>>,
std::greater<>>
pq; // should be empty outside of dual()
std::vector<V_id> ev, dv;
Edge &rev(const Edge &e) { return g[e.dst][e.rev]; }
void push(Edge &e, const Flow amt) {
e.flw += amt;
g[e.dst][e.rev].flw -= amt;
}
Cost residual_cost(const V_id src, const V_id dst, const Edge &e) {
return e.cst + pot[src] - pot[dst];
}
bool dual(const Flow dlt) {
dis.assign(n, inf);
fa.assign(n, nullptr);
ev.erase(std::remove_if(std::begin(ev), std::end(ev),
[&](const V_id v) { return b[v] < dlt; }),
std::end(ev));
dv.erase(std::remove_if(std::begin(dv), std::end(dv),
[&](const V_id v) { return b[v] > -dlt; }),
std::end(dv));
for (const auto v : ev)
pq.emplace(dis[v] = 0, v);
far = 0;
std::size_t nd = 0;
while (!pq.empty()) {
Cost d;
std::size_t u;
std::tie(d, u) = pq.top();
// const auto [d, u] = pq.top();
pq.pop();
if (dis[u] < d)
continue;
far = d;
if (b[u] <= -dlt)
++nd;
if (nd >= dv.size())
break;
for (auto &e : g[u]) {
if (e.residual_cap() < dlt)
continue;
const auto v = e.dst;
const auto vtx = d + residual_cost(u, v, e);
if (vtx >= dis[v])
continue;
pq.emplace(dis[v] = vtx, v);
fa[v] = &e;
}
}
pq = decltype(pq)(); // pq.clear() doesn't exist.
for (V_id v = 0; v < n; ++v) {
pot[v] += std::min(dis[v], far);
}
return nd > 0;
}
void primal(const Flow dlt) {
for (const auto t : dv) {
if (dis[t] > far)
continue;
Flow f = -b[t];
V_id v;
for (v = t; fa[v] != nullptr; v = fa[v]->src) {
f = std::min(f, fa[v]->residual_cap());
}
f = std::min(f, b[v]);
f -= f % dlt;
if (f <= 0)
continue;
for (v = t; fa[v] != nullptr;) {
auto &e = *fa[v];
push(e, f);
int u = fa[v]->src;
if (e.residual_cap() <= 0)
fa[v] = nullptr;
v = u;
}
b[t] += f;
b[v] -= f;
}
}
void saturate_negative(const Flow dlt) {
ev.clear();
dv.clear();
for (auto &es : g)
for (auto &e : es) {
Flow ca1 = e.residual_cap();
ca1 -= ca1 % dlt;
const Cost cs1 = residual_cost(e.src, e.dst, e);
if (cs1 < 0 || ca1 < 0) {
push(e, ca1);
b[e.src] -= ca1;
b[e.dst] += ca1;
}
}
for (V_id v = 0; v < n; ++v)
if (b[v] != 0) {
(b[v] > 0 ? ev : dv).emplace_back(v);
}
}
public:
std::pair<Status, Cost> solve() {
pot.resize(n);
Flow in1 = 1;
for (const auto t : b)
in1 = std::max({in1, t, -t});
for (const auto &es : g)
for (const auto &e : es)
in1 = std::max({in1, e.residual_cap(), -e.residual_cap()});
Flow dlt = 1;
while (dlt < in1)
dlt *= SCALING_FACTOR;
for (; dlt; dlt /= SCALING_FACTOR) {
saturate_negative(dlt);
while (dual(dlt))
primal(dlt);
}
Cost val = 0;
for (const auto &es : g)
for (const auto &e : es) {
val += e.flw * e.cst;
}
val /= 2;
if (ev.empty() && dv.empty()) {
return {Status::OPTIMAL, val / objective};
} else {
return {Status::INFEASIBLE, val / objective};
}
}
std::vector<Cost> get_potential() {
// Not strictly necessary, but re-calculate pot to bound the pot values,
// plus make them somewhat canonical so that it is robust for the algorithm chaneges.
std::fill(std::begin(pot), std::end(pot), 0);
for (size_t i = 0; i < n; ++i)
for (const auto &es : g)
for (const auto &e : es)
if (e.residual_cap() > 0)
pot[e.dst] = std::min(pot[e.dst], pot[e.src] + e.cst);
return pot;
}
template <class T> T get_result_value() {
T val = 0;
for (const auto &es : g)
for (const auto &e : es) {
val += (T)(e.flw) * (T)(e.cst);
}
val /= (T)2;
return val;
}
std::vector<size_t> get_cut() {
std::vector<size_t> res;
if (ev.empty())
return res;
for (size_t v = 0; v < n; ++v) {
if (dv.empty() || (dis[v] < inf))
res.emplace_back(v);
}
return res;
}
};
} // namespace noya