lower_bound_flow.hpp¶
处理每条边带下界和上界的可行环流或最大流；用于必须至少运送一定流量的网络。
Complexity: Time: \(O(n + m)\) preparation and at most two Dinic runs, \(O(V^{2} E)\) worst case, where \(V = n + 2\) and \(E \le m + n + 1\). Space: \(O(n + m)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + m) preparation and at most two Dinic runs,
/// O(V^2 E) worst case, where V=n+2 and E<=m+n+1. Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief A feasible or maximum flow together with every original edge flow.
template <class Cap> struct lower_bound_flow_result {
Cap val{};
std::vector<Cap> flw;
};
/// @brief Nonnegative lower/upper bounds, with Dinic on a CSR graph.
/// The maximum nonnegative flow must fit Cap; arithmetic must be exact.
/// Integer demand sums use up to unsigned 128 bits when Cap is insufficient.
/// Each vertex's incoming/outgoing lower sum and total positive demand must
/// fit that internal type. Vertices and residual arcs must fit int.
/// Blocking-flow DFS has O(n) call depth; use the 512 MiB test stack.
template <class Cap> struct lower_bound_flow {
struct edge {
int u;
int to;
Cap lo;
Cap hi;
};
int n = 0;
std::vector<edge> es;
lower_bound_flow() = default;
explicit lower_bound_flow(int n_) : n(n_) { assert(n >= 0); }
/// @brief Add a directed edge with lo <= flow <= hi and return its id.
int add_edge(int u, int to, Cap lo, Cap hi) {
assert(0 <= u && u < n);
assert(0 <= to && to < n);
assert(Cap{} <= lo && lo <= hi);
assert(es.size() < std::size_t(std::numeric_limits<int>::max()));
int id = int(es.size());
es.push_back({u, to, lo, hi});
return id;
}
/// @brief Return one feasible circulation, or nullopt if none exists.
std::optional<std::vector<Cap>> feasible_circulation() const {
auto res = dispatch(-1, -1);
if (!res) return std::nullopt;
return std::move(res->flw);
}
/// @brief Return a maximum nonnegative source-to-sink flow and its edge
/// flows, or nullopt when no such feasible flow exists.
std::optional<lower_bound_flow_result<Cap>> max_flow(int s, int t) const {
assert(0 <= s && s < n);
assert(0 <= t && t < n);
assert(s != t);
return dispatch(s, t);
}
private:
template <class D> struct network {
int n;
std::vector<int> to, head, adj, level, it, queue;
std::vector<D> cap;
network(int count, std::size_t edges)
: n(count), head(std::size_t(count) + 1), level(count), it(count),
queue(count) {
assert(edges <= std::size_t(std::numeric_limits<int>::max()) / 2);
to.reserve(2 * edges);
cap.reserve(2 * edges);
}
int add_edge(int u, int v, D c) {
int id = int(cap.size()) / 2;
to.push_back(v);
cap.push_back(c);
to.push_back(u);
cap.push_back(D{});
++head[u + 1];
++head[v + 1];
return id;
}
void prepare() {
std::partial_sum(head.begin(), head.end(), head.begin());
auto at = head;
adj.resize(to.size());
for (int a = 0; a < int(to.size()); ++a) {
adj[at[to[a ^ 1]]++] = a;
}
}
D edge_flow(int id) const { return cap[2 * id + 1]; }
void erase_since(int id) {
std::fill(cap.begin() + 2 * id, cap.end(), D{});
}
// Traverse backward from the sink, matching ACL's blocking-flow order.
D dfs(int v, int source, D up) {
if (v == source) return up;
D sent{};
for (int &j = it[v]; j < head[v + 1]; ++j) {
int a = adj[j], u = to[a];
if (level[v] <= level[u] || cap[a ^ 1] == D{}) continue;
D d = dfs(u, source, std::min<D>(up - sent, cap[a ^ 1]));
cap[a] += d;
cap[a ^ 1] -= d;
sent += d;
if (sent == up) return sent;
}
level[v] = n;
return sent;
}
D flow(int source, int target, D limit) {
D total{};
while (total < limit) {
std::fill(level.begin(), level.end(), -1);
level[source] = 0;
int first = 0, last = 0;
queue[last++] = source;
while (first < last && level[target] < 0) {
int v = queue[first++];
for (int j = head[v]; j < head[v + 1]; ++j) {
int a = adj[j], u = to[a];
if (cap[a] == D{} || level[u] >= 0) continue;
level[u] = level[v] + 1;
if (u == target) break;
queue[last++] = u;
}
}
if (level[target] < 0) break;
std::copy_n(head.begin(), n, it.begin());
D sent = dfs(target, source, limit - total);
if (sent == D{}) break;
total += sent;
}
return total;
}
};
using result = std::optional<lower_bound_flow_result<Cap>>;
result dispatch(int s, int t) const {
if constexpr (std::numeric_limits<Cap>::is_integer) {
using wide = std::conditional_t<(sizeof(Cap) < sizeof(std::uint64_t)),
std::uint64_t, __uint128_t>;
if constexpr (!std::is_same_v<Cap, wide>) {
// A conservative bound: all lower sums and demand fit if this fits.
// Upper bounds (often INF) need not contribute to this bound.
Cap sum{};
for (const edge &e : es) {
if (e.u == e.to) continue;
if (e.lo > std::numeric_limits<Cap>::max() - sum) {
return solve<wide>(s, t);
}
sum += e.lo;
}
}
}
return solve<Cap>(s, t);
}
template <class D> result solve(int s, int t) const {
assert(0 <= n && n <= std::numeric_limits<int>::max() - 2);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
const bool maximum = s >= 0;
lower_bound_flow_result<Cap> res;
if (es.empty()) return res;
res.flw.reserve(es.size());
std::vector<D> incoming(n), outgoing(n);
int active = 0;
auto add = [](D &a, D b) {
assert(b <= std::numeric_limits<D>::max() - a);
a += b;
};
for (const edge &e : es) {
assert(0 <= e.u && e.u < n && 0 <= e.to && e.to < n);
assert(Cap{} <= e.lo && e.lo <= e.hi);
res.flw.push_back(e.lo);
if (e.u == e.to) continue;
add(incoming[e.to], D(e.lo));
add(outgoing[e.u], D(e.lo));
active += e.hi != e.lo;
}
D need{};
int aux = 0;
for (int v = 0; v < n; ++v) {
aux += incoming[v] != outgoing[v];
if (incoming[v] > outgoing[v]) {
add(need, incoming[v] - outgoing[v]);
}
}
if (need == D{} && (!maximum || active == 0)) return res;
network<D> net(n + 2, std::size_t(active) + aux + (maximum && need != D{}));
std::vector<int> original;
original.reserve(active);
for (int i = 0; i < int(es.size()); ++i) {
const edge &e = es[i];
if (e.u != e.to && e.lo != e.hi) {
net.add_edge(e.u, e.to, D(e.hi - e.lo));
original.push_back(i);
}
}
for (int v = 0; v < n; ++v) {
if (incoming[v] > outgoing[v]) {
net.add_edge(n, v, incoming[v] - outgoing[v]);
} else if (incoming[v] < outgoing[v]) {
net.add_edge(v, n + 1, outgoing[v] - incoming[v]);
}
}
const D limit = D(std::numeric_limits<Cap>::max());
int back = -1;
if (maximum && need != D{}) back = net.add_edge(t, s, limit);
net.prepare();
if (need != D{} && net.flow(n, n + 1, need) != need) return std::nullopt;
if (maximum) {
D value = back < 0 ? D{} : net.edge_flow(back);
net.erase_since(active);
assert(value <= limit);
value += net.flow(s, t, limit - value);
res.val = Cap(value);
}
for (int id = 0; id < active; ++id) {
res.flw[original[id]] += Cap(net.edge_flow(id));
}
return res;
}
};
} // namespace noya
// NOYA_LOWER_BOUND_FLOW_HPP
#ifndef NOYA_LOWER_BOUND_FLOW_HPP
#define NOYA_LOWER_BOUND_FLOW_HPP 1
/// @complexity Time: O(n + m) preparation and at most two Dinic runs,
/// O(V^2 E) worst case, where V=n+2 and E<=m+n+1. Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief A feasible or maximum flow together with every original edge flow.
template <class Cap> struct lower_bound_flow_result {
Cap val{};
std::vector<Cap> flw;
};
/// @brief Nonnegative lower/upper bounds, with Dinic on a CSR graph.
/// The maximum nonnegative flow must fit Cap; arithmetic must be exact.
/// Integer demand sums use up to unsigned 128 bits when Cap is insufficient.
/// Each vertex's incoming/outgoing lower sum and total positive demand must
/// fit that internal type. Vertices and residual arcs must fit int.
/// Blocking-flow DFS has O(n) call depth; use the 512 MiB test stack.
template <class Cap> struct lower_bound_flow {
struct edge {
int u;
int to;
Cap lo;
Cap hi;
};
int n = 0;
std::vector<edge> es;
lower_bound_flow() = default;
explicit lower_bound_flow(int n_) : n(n_) { assert(n >= 0); }
/// @brief Add a directed edge with lo <= flow <= hi and return its id.
int add_edge(int u, int to, Cap lo, Cap hi) {
assert(0 <= u && u < n);
assert(0 <= to && to < n);
assert(Cap{} <= lo && lo <= hi);
assert(es.size() < std::size_t(std::numeric_limits<int>::max()));
int id = int(es.size());
es.push_back({u, to, lo, hi});
return id;
}
/// @brief Return one feasible circulation, or nullopt if none exists.
std::optional<std::vector<Cap>> feasible_circulation() const {
auto res = dispatch(-1, -1);
if (!res) return std::nullopt;
return std::move(res->flw);
}
/// @brief Return a maximum nonnegative source-to-sink flow and its edge
/// flows, or nullopt when no such feasible flow exists.
std::optional<lower_bound_flow_result<Cap>> max_flow(int s, int t) const {
assert(0 <= s && s < n);
assert(0 <= t && t < n);
assert(s != t);
return dispatch(s, t);
}
private:
template <class D> struct network {
int n;
std::vector<int> to, head, adj, level, it, queue;
std::vector<D> cap;
network(int count, std::size_t edges)
: n(count), head(std::size_t(count) + 1), level(count), it(count),
queue(count) {
assert(edges <= std::size_t(std::numeric_limits<int>::max()) / 2);
to.reserve(2 * edges);
cap.reserve(2 * edges);
}
int add_edge(int u, int v, D c) {
int id = int(cap.size()) / 2;
to.push_back(v);
cap.push_back(c);
to.push_back(u);
cap.push_back(D{});
++head[u + 1];
++head[v + 1];
return id;
}
void prepare() {
std::partial_sum(head.begin(), head.end(), head.begin());
auto at = head;
adj.resize(to.size());
for (int a = 0; a < int(to.size()); ++a) {
adj[at[to[a ^ 1]]++] = a;
}
}
D edge_flow(int id) const { return cap[2 * id + 1]; }
void erase_since(int id) {
std::fill(cap.begin() + 2 * id, cap.end(), D{});
}
// Traverse backward from the sink, matching ACL's blocking-flow order.
D dfs(int v, int source, D up) {
if (v == source) return up;
D sent{};
for (int &j = it[v]; j < head[v + 1]; ++j) {
int a = adj[j], u = to[a];
if (level[v] <= level[u] || cap[a ^ 1] == D{}) continue;
D d = dfs(u, source, std::min<D>(up - sent, cap[a ^ 1]));
cap[a] += d;
cap[a ^ 1] -= d;
sent += d;
if (sent == up) return sent;
}
level[v] = n;
return sent;
}
D flow(int source, int target, D limit) {
D total{};
while (total < limit) {
std::fill(level.begin(), level.end(), -1);
level[source] = 0;
int first = 0, last = 0;
queue[last++] = source;
while (first < last && level[target] < 0) {
int v = queue[first++];
for (int j = head[v]; j < head[v + 1]; ++j) {
int a = adj[j], u = to[a];
if (cap[a] == D{} || level[u] >= 0) continue;
level[u] = level[v] + 1;
if (u == target) break;
queue[last++] = u;
}
}
if (level[target] < 0) break;
std::copy_n(head.begin(), n, it.begin());
D sent = dfs(target, source, limit - total);
if (sent == D{}) break;
total += sent;
}
return total;
}
};
using result = std::optional<lower_bound_flow_result<Cap>>;
result dispatch(int s, int t) const {
if constexpr (std::numeric_limits<Cap>::is_integer) {
using wide = std::conditional_t<(sizeof(Cap) < sizeof(std::uint64_t)),
std::uint64_t, __uint128_t>;
if constexpr (!std::is_same_v<Cap, wide>) {
// A conservative bound: all lower sums and demand fit if this fits.
// Upper bounds (often INF) need not contribute to this bound.
Cap sum{};
for (const edge &e : es) {
if (e.u == e.to) continue;
if (e.lo > std::numeric_limits<Cap>::max() - sum) {
return solve<wide>(s, t);
}
sum += e.lo;
}
}
}
return solve<Cap>(s, t);
}
template <class D> result solve(int s, int t) const {
assert(0 <= n && n <= std::numeric_limits<int>::max() - 2);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
const bool maximum = s >= 0;
lower_bound_flow_result<Cap> res;
if (es.empty()) return res;
res.flw.reserve(es.size());
std::vector<D> incoming(n), outgoing(n);
int active = 0;
auto add = [](D &a, D b) {
assert(b <= std::numeric_limits<D>::max() - a);
a += b;
};
for (const edge &e : es) {
assert(0 <= e.u && e.u < n && 0 <= e.to && e.to < n);
assert(Cap{} <= e.lo && e.lo <= e.hi);
res.flw.push_back(e.lo);
if (e.u == e.to) continue;
add(incoming[e.to], D(e.lo));
add(outgoing[e.u], D(e.lo));
active += e.hi != e.lo;
}
D need{};
int aux = 0;
for (int v = 0; v < n; ++v) {
aux += incoming[v] != outgoing[v];
if (incoming[v] > outgoing[v]) {
add(need, incoming[v] - outgoing[v]);
}
}
if (need == D{} && (!maximum || active == 0)) return res;
network<D> net(n + 2, std::size_t(active) + aux + (maximum && need != D{}));
std::vector<int> original;
original.reserve(active);
for (int i = 0; i < int(es.size()); ++i) {
const edge &e = es[i];
if (e.u != e.to && e.lo != e.hi) {
net.add_edge(e.u, e.to, D(e.hi - e.lo));
original.push_back(i);
}
}
for (int v = 0; v < n; ++v) {
if (incoming[v] > outgoing[v]) {
net.add_edge(n, v, incoming[v] - outgoing[v]);
} else if (incoming[v] < outgoing[v]) {
net.add_edge(v, n + 1, outgoing[v] - incoming[v]);
}
}
const D limit = D(std::numeric_limits<Cap>::max());
int back = -1;
if (maximum && need != D{}) back = net.add_edge(t, s, limit);
net.prepare();
if (need != D{} && net.flow(n, n + 1, need) != need) return std::nullopt;
if (maximum) {
D value = back < 0 ? D{} : net.edge_flow(back);
net.erase_since(active);
assert(value <= limit);
value += net.flow(s, t, limit - value);
res.val = Cap(value);
}
for (int id = 0; id < active; ++id) {
res.flw[original[id]] += Cap(net.edge_flow(id));
}
return res;
}
};
} // namespace noya
#endif // NOYA_LOWER_BOUND_FLOW_HPP
/// @complexity Time: O(n + m) preparation and at most two Dinic runs,
/// O(V^2 E) worst case, where V=n+2 and E<=m+n+1. Space: O(n + m).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief A feasible or maximum flow together with every original edge flow.
template <class Cap> struct lower_bound_flow_result {
Cap val{};
std::vector<Cap> flw;
};
/// @brief Nonnegative lower/upper bounds, with Dinic on a CSR graph.
/// The maximum nonnegative flow must fit Cap; arithmetic must be exact.
/// Integer demand sums use up to unsigned 128 bits when Cap is insufficient.
/// Each vertex's incoming/outgoing lower sum and total positive demand must
/// fit that internal type. Vertices and residual arcs must fit int.
/// Blocking-flow DFS has O(n) call depth; use the 512 MiB test stack.
template <class Cap> struct lower_bound_flow {
struct edge {
int u;
int to;
Cap lo;
Cap hi;
};
int n = 0;
std::vector<edge> es;
lower_bound_flow() = default;
explicit lower_bound_flow(int n_) : n(n_) { assert(n >= 0); }
/// @brief Add a directed edge with lo <= flow <= hi and return its id.
int add_edge(int u, int to, Cap lo, Cap hi) {
assert(0 <= u && u < n);
assert(0 <= to && to < n);
assert(Cap{} <= lo && lo <= hi);
assert(es.size() < std::size_t(std::numeric_limits<int>::max()));
int id = int(es.size());
es.push_back({u, to, lo, hi});
return id;
}
/// @brief Return one feasible circulation, or nullopt if none exists.
std::optional<std::vector<Cap>> feasible_circulation() const {
auto res = dispatch(-1, -1);
if (!res) return std::nullopt;
return std::move(res->flw);
}
/// @brief Return a maximum nonnegative source-to-sink flow and its edge
/// flows, or nullopt when no such feasible flow exists.
std::optional<lower_bound_flow_result<Cap>> max_flow(int s, int t) const {
assert(0 <= s && s < n);
assert(0 <= t && t < n);
assert(s != t);
return dispatch(s, t);
}
private:
template <class D> struct network {
int n;
std::vector<int> to, head, adj, level, it, queue;
std::vector<D> cap;
network(int count, std::size_t edges)
: n(count), head(std::size_t(count) + 1), level(count), it(count),
queue(count) {
assert(edges <= std::size_t(std::numeric_limits<int>::max()) / 2);
to.reserve(2 * edges);
cap.reserve(2 * edges);
}
int add_edge(int u, int v, D c) {
int id = int(cap.size()) / 2;
to.push_back(v);
cap.push_back(c);
to.push_back(u);
cap.push_back(D{});
++head[u + 1];
++head[v + 1];
return id;
}
void prepare() {
std::partial_sum(head.begin(), head.end(), head.begin());
auto at = head;
adj.resize(to.size());
for (int a = 0; a < int(to.size()); ++a) {
adj[at[to[a ^ 1]]++] = a;
}
}
D edge_flow(int id) const { return cap[2 * id + 1]; }
void erase_since(int id) {
std::fill(cap.begin() + 2 * id, cap.end(), D{});
}
// Traverse backward from the sink, matching ACL's blocking-flow order.
D dfs(int v, int source, D up) {
if (v == source) return up;
D sent{};
for (int &j = it[v]; j < head[v + 1]; ++j) {
int a = adj[j], u = to[a];
if (level[v] <= level[u] || cap[a ^ 1] == D{}) continue;
D d = dfs(u, source, std::min<D>(up - sent, cap[a ^ 1]));
cap[a] += d;
cap[a ^ 1] -= d;
sent += d;
if (sent == up) return sent;
}
level[v] = n;
return sent;
}
D flow(int source, int target, D limit) {
D total{};
while (total < limit) {
std::fill(level.begin(), level.end(), -1);
level[source] = 0;
int first = 0, last = 0;
queue[last++] = source;
while (first < last && level[target] < 0) {
int v = queue[first++];
for (int j = head[v]; j < head[v + 1]; ++j) {
int a = adj[j], u = to[a];
if (cap[a] == D{} || level[u] >= 0) continue;
level[u] = level[v] + 1;
if (u == target) break;
queue[last++] = u;
}
}
if (level[target] < 0) break;
std::copy_n(head.begin(), n, it.begin());
D sent = dfs(target, source, limit - total);
if (sent == D{}) break;
total += sent;
}
return total;
}
};
using result = std::optional<lower_bound_flow_result<Cap>>;
result dispatch(int s, int t) const {
if constexpr (std::numeric_limits<Cap>::is_integer) {
using wide = std::conditional_t<(sizeof(Cap) < sizeof(std::uint64_t)),
std::uint64_t, __uint128_t>;
if constexpr (!std::is_same_v<Cap, wide>) {
// A conservative bound: all lower sums and demand fit if this fits.
// Upper bounds (often INF) need not contribute to this bound.
Cap sum{};
for (const edge &e : es) {
if (e.u == e.to) continue;
if (e.lo > std::numeric_limits<Cap>::max() - sum) {
return solve<wide>(s, t);
}
sum += e.lo;
}
}
}
return solve<Cap>(s, t);
}
template <class D> result solve(int s, int t) const {
assert(0 <= n && n <= std::numeric_limits<int>::max() - 2);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
const bool maximum = s >= 0;
lower_bound_flow_result<Cap> res;
if (es.empty()) return res;
res.flw.reserve(es.size());
std::vector<D> incoming(n), outgoing(n);
int active = 0;
auto add = [](D &a, D b) {
assert(b <= std::numeric_limits<D>::max() - a);
a += b;
};
for (const edge &e : es) {
assert(0 <= e.u && e.u < n && 0 <= e.to && e.to < n);
assert(Cap{} <= e.lo && e.lo <= e.hi);
res.flw.push_back(e.lo);
if (e.u == e.to) continue;
add(incoming[e.to], D(e.lo));
add(outgoing[e.u], D(e.lo));
active += e.hi != e.lo;
}
D need{};
int aux = 0;
for (int v = 0; v < n; ++v) {
aux += incoming[v] != outgoing[v];
if (incoming[v] > outgoing[v]) {
add(need, incoming[v] - outgoing[v]);
}
}
if (need == D{} && (!maximum || active == 0)) return res;
network<D> net(n + 2, std::size_t(active) + aux + (maximum && need != D{}));
std::vector<int> original;
original.reserve(active);
for (int i = 0; i < int(es.size()); ++i) {
const edge &e = es[i];
if (e.u != e.to && e.lo != e.hi) {
net.add_edge(e.u, e.to, D(e.hi - e.lo));
original.push_back(i);
}
}
for (int v = 0; v < n; ++v) {
if (incoming[v] > outgoing[v]) {
net.add_edge(n, v, incoming[v] - outgoing[v]);
} else if (incoming[v] < outgoing[v]) {
net.add_edge(v, n + 1, outgoing[v] - incoming[v]);
}
}
const D limit = D(std::numeric_limits<Cap>::max());
int back = -1;
if (maximum && need != D{}) back = net.add_edge(t, s, limit);
net.prepare();
if (need != D{} && net.flow(n, n + 1, need) != need) return std::nullopt;
if (maximum) {
D value = back < 0 ? D{} : net.edge_flow(back);
net.erase_since(active);
assert(value <= limit);
value += net.flow(s, t, limit - value);
res.val = Cap(value);
}
for (int id = 0; id < active; ++id) {
res.flw[original[id]] += Cap(net.edge_flow(id));
}
return res;
}
};
} // namespace noya
// NOYA_LOWER_BOUND_FLOW_HPP