lower_bound_flow.hpp¶
处理每条边带下界和上界的可行环流或最大流；用于必须至少运送一定流量的网络。
Complexity: Time: One or two maximum-flow runs; Dinic worst case O(V^2 E). Space: O(V + E).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: One or two maximum-flow runs; Dinic worst case O(V^2 E).
/// Space: O(V + E).
#include "atcoder/maxflow.hpp"
#include <cassert>
#include <limits>
#include <optional>
#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 Directed flow network with lower and upper edge bounds; feasibility
/// and maximum-flow reductions use AtCoder Library's max-flow implementation.
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);
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 {
built_network net = build_network();
if (!satisfy_demands(net)) {
return std::nullopt;
}
return recover_edge_flows(net);
}
/// @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);
built_network net = build_network();
int re = net.g.add_edge(t, s, std::numeric_limits<Cap>::max());
if (!satisfy_demands(net)) {
return std::nullopt;
}
Cap ini = net.g.get_edge(re).flow;
for (int id : net.aux) {
net.g.change_edge(id, Cap{}, Cap{});
}
net.g.change_edge(re, Cap{}, Cap{});
Cap ext = net.g.flow(s, t);
return lower_bound_flow_result<Cap>{ini + ext, recover_edge_flows(net)};
}
private:
struct built_network {
atcoder::mf_graph<Cap> g;
int ss;
int tt;
Cap td{};
std::vector<int> oe;
std::vector<int> aux;
explicit built_network(int n) : g(n + 2), ss(n), tt(n + 1) {}
};
built_network build_network() const {
built_network res(n);
std::vector<Cap> ri(n);
std::vector<Cap> ro(n);
res.oe.reserve(es.size());
for (const edge &cur : es) {
res.oe.push_back(res.g.add_edge(cur.u, cur.to, cur.hi - cur.lo));
ro[cur.u] += cur.lo;
ri[cur.to] += cur.lo;
}
for (int v = 0; v < n; v++) {
if (ri[v] > ro[v]) {
Cap dem = ri[v] - ro[v];
res.aux.push_back(res.g.add_edge(res.ss, v, dem));
res.td += dem;
} else if (ro[v] > ri[v]) {
res.aux.push_back(res.g.add_edge(v, res.tt, ro[v] - ri[v]));
}
}
return res;
}
static bool satisfy_demands(built_network &net) {
return net.g.flow(net.ss, net.tt) == net.td;
}
std::vector<Cap> recover_edge_flows(built_network &net) const {
std::vector<Cap> res(es.size());
for (int id = 0; id < int(es.size()); id++) {
res[id] = es[id].lo + net.g.get_edge(net.oe[id]).flow;
}
return res;
}
};
} // namespace noya
#ifndef NOYA_LOWER_BOUND_FLOW_HPP
#define NOYA_LOWER_BOUND_FLOW_HPP 1
/// @complexity Time: One or two maximum-flow runs; Dinic worst case O(V^2 E).
/// Space: O(V + E).
#include "atcoder/maxflow.hpp"
#include <cassert>
#include <limits>
#include <optional>
#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 Directed flow network with lower and upper edge bounds; feasibility
/// and maximum-flow reductions use AtCoder Library's max-flow implementation.
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);
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 {
built_network net = build_network();
if (!satisfy_demands(net)) {
return std::nullopt;
}
return recover_edge_flows(net);
}
/// @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);
built_network net = build_network();
int re = net.g.add_edge(t, s, std::numeric_limits<Cap>::max());
if (!satisfy_demands(net)) {
return std::nullopt;
}
Cap ini = net.g.get_edge(re).flow;
for (int id : net.aux) {
net.g.change_edge(id, Cap{}, Cap{});
}
net.g.change_edge(re, Cap{}, Cap{});
Cap ext = net.g.flow(s, t);
return lower_bound_flow_result<Cap>{ini + ext, recover_edge_flows(net)};
}
private:
struct built_network {
atcoder::mf_graph<Cap> g;
int ss;
int tt;
Cap td{};
std::vector<int> oe;
std::vector<int> aux;
explicit built_network(int n) : g(n + 2), ss(n), tt(n + 1) {}
};
built_network build_network() const {
built_network res(n);
std::vector<Cap> ri(n);
std::vector<Cap> ro(n);
res.oe.reserve(es.size());
for (const edge &cur : es) {
res.oe.push_back(res.g.add_edge(cur.u, cur.to, cur.hi - cur.lo));
ro[cur.u] += cur.lo;
ri[cur.to] += cur.lo;
}
for (int v = 0; v < n; v++) {
if (ri[v] > ro[v]) {
Cap dem = ri[v] - ro[v];
res.aux.push_back(res.g.add_edge(res.ss, v, dem));
res.td += dem;
} else if (ro[v] > ri[v]) {
res.aux.push_back(res.g.add_edge(v, res.tt, ro[v] - ri[v]));
}
}
return res;
}
static bool satisfy_demands(built_network &net) {
return net.g.flow(net.ss, net.tt) == net.td;
}
std::vector<Cap> recover_edge_flows(built_network &net) const {
std::vector<Cap> res(es.size());
for (int id = 0; id < int(es.size()); id++) {
res[id] = es[id].lo + net.g.get_edge(net.oe[id]).flow;
}
return res;
}
};
} // namespace noya
#endif // NOYA_LOWER_BOUND_FLOW_HPP
#include <algorithm>
#include <cassert>
#include <limits>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: One or two maximum-flow runs; Dinic worst case O(V^2 E).
/// Space: O(V + E).
namespace atcoder {
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
explicit mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{to, to_id, cap});
g[to].push_back(_edge{from, from_id, 0});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = int(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto& _e = g[pos[i].first][pos[i].second];
auto& _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int& i = iter[v]; i < int(g[v].size()); i++) {
_edge& e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) return res;
}
level[v] = _n;
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
} // namespace atcoder
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 Directed flow network with lower and upper edge bounds; feasibility
/// and maximum-flow reductions use AtCoder Library's max-flow implementation.
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);
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 {
built_network net = build_network();
if (!satisfy_demands(net)) {
return std::nullopt;
}
return recover_edge_flows(net);
}
/// @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);
built_network net = build_network();
int re = net.g.add_edge(t, s, std::numeric_limits<Cap>::max());
if (!satisfy_demands(net)) {
return std::nullopt;
}
Cap ini = net.g.get_edge(re).flow;
for (int id : net.aux) {
net.g.change_edge(id, Cap{}, Cap{});
}
net.g.change_edge(re, Cap{}, Cap{});
Cap ext = net.g.flow(s, t);
return lower_bound_flow_result<Cap>{ini + ext, recover_edge_flows(net)};
}
private:
struct built_network {
atcoder::mf_graph<Cap> g;
int ss;
int tt;
Cap td{};
std::vector<int> oe;
std::vector<int> aux;
explicit built_network(int n) : g(n + 2), ss(n), tt(n + 1) {}
};
built_network build_network() const {
built_network res(n);
std::vector<Cap> ri(n);
std::vector<Cap> ro(n);
res.oe.reserve(es.size());
for (const edge &cur : es) {
res.oe.push_back(res.g.add_edge(cur.u, cur.to, cur.hi - cur.lo));
ro[cur.u] += cur.lo;
ri[cur.to] += cur.lo;
}
for (int v = 0; v < n; v++) {
if (ri[v] > ro[v]) {
Cap dem = ri[v] - ro[v];
res.aux.push_back(res.g.add_edge(res.ss, v, dem));
res.td += dem;
} else if (ro[v] > ri[v]) {
res.aux.push_back(res.g.add_edge(v, res.tt, ro[v] - ri[v]));
}
}
return res;
}
static bool satisfy_demands(built_network &net) {
return net.g.flow(net.ss, net.tt) == net.td;
}
std::vector<Cap> recover_edge_flows(built_network &net) const {
std::vector<Cap> res(es.size());
for (int id = 0; id < int(es.size()); id++) {
res[id] = es[id].lo + net.g.get_edge(net.oe[id]).flow;
}
return res;
}
};
} // namespace noya