lower_bound_flow.hpp¶
Feasible circulation and maximum flow with lower and upper edge bounds.
处理每条边带下界和上界的可行环流或最大流；用于必须至少运送一定流量的网络。
Implementation¶
#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 value{};
std::vector<Cap> edge_flow;
};
/// @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 from;
int to;
Cap lower;
Cap upper;
};
int n = 0;
std::vector<edge> edges;
lower_bound_flow() = default;
explicit lower_bound_flow(int n_) : n(n_) { assert(n >= 0); }
/// @brief Add a directed edge with lower <= flow <= upper and return its id.
int add_edge(int from, int to, Cap lower, Cap upper) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
assert(Cap{} <= lower && lower <= upper);
int id = int(edges.size());
edges.push_back({from, to, lower, upper});
return id;
}
/// @brief Return one feasible circulation, or nullopt if none exists.
std::optional<std::vector<Cap>> feasible_circulation() const {
built_network network = build_network();
if (!satisfy_demands(network)) {
return std::nullopt;
}
return recover_edge_flows(network);
}
/// @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 source,
int sink) const {
assert(0 <= source && source < n);
assert(0 <= sink && sink < n);
assert(source != sink);
built_network network = build_network();
int return_edge = network.graph.add_edge(
sink, source, std::numeric_limits<Cap>::max());
if (!satisfy_demands(network)) {
return std::nullopt;
}
Cap initial = network.graph.get_edge(return_edge).flow;
for (int id : network.auxiliary_edges) {
network.graph.change_edge(id, Cap{}, Cap{});
}
network.graph.change_edge(return_edge, Cap{}, Cap{});
Cap additional = network.graph.flow(source, sink);
return lower_bound_flow_result<Cap>{
initial + additional, recover_edge_flows(network)};
}
private:
struct built_network {
atcoder::mf_graph<Cap> graph;
int super_source;
int super_sink;
Cap total_demand{};
std::vector<int> original_edges;
std::vector<int> auxiliary_edges;
explicit built_network(int n)
: graph(n + 2), super_source(n), super_sink(n + 1) {}
};
built_network build_network() const {
built_network result(n);
std::vector<Cap> required_in(n);
std::vector<Cap> required_out(n);
result.original_edges.reserve(edges.size());
for (const edge ¤t : edges) {
result.original_edges.push_back(result.graph.add_edge(
current.from, current.to, current.upper - current.lower));
required_out[current.from] += current.lower;
required_in[current.to] += current.lower;
}
for (int vertex = 0; vertex < n; vertex++) {
if (required_in[vertex] > required_out[vertex]) {
Cap demand = required_in[vertex] - required_out[vertex];
result.auxiliary_edges.push_back(
result.graph.add_edge(result.super_source, vertex, demand));
result.total_demand += demand;
} else if (required_out[vertex] > required_in[vertex]) {
result.auxiliary_edges.push_back(result.graph.add_edge(
vertex, result.super_sink,
required_out[vertex] - required_in[vertex]));
}
}
return result;
}
static bool satisfy_demands(built_network &network) {
return network.graph.flow(network.super_source, network.super_sink) ==
network.total_demand;
}
std::vector<Cap> recover_edge_flows(built_network &network) const {
std::vector<Cap> result(edges.size());
for (int id = 0; id < int(edges.size()); id++) {
result[id] = edges[id].lower +
network.graph.get_edge(network.original_edges[id]).flow;
}
return result;
}
};
} // 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 value{};
std::vector<Cap> edge_flow;
};
/// @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 from;
int to;
Cap lower;
Cap upper;
};
int n = 0;
std::vector<edge> edges;
lower_bound_flow() = default;
explicit lower_bound_flow(int n_) : n(n_) { assert(n >= 0); }
/// @brief Add a directed edge with lower <= flow <= upper and return its id.
int add_edge(int from, int to, Cap lower, Cap upper) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
assert(Cap{} <= lower && lower <= upper);
int id = int(edges.size());
edges.push_back({from, to, lower, upper});
return id;
}
/// @brief Return one feasible circulation, or nullopt if none exists.
std::optional<std::vector<Cap>> feasible_circulation() const {
built_network network = build_network();
if (!satisfy_demands(network)) {
return std::nullopt;
}
return recover_edge_flows(network);
}
/// @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 source,
int sink) const {
assert(0 <= source && source < n);
assert(0 <= sink && sink < n);
assert(source != sink);
built_network network = build_network();
int return_edge = network.graph.add_edge(
sink, source, std::numeric_limits<Cap>::max());
if (!satisfy_demands(network)) {
return std::nullopt;
}
Cap initial = network.graph.get_edge(return_edge).flow;
for (int id : network.auxiliary_edges) {
network.graph.change_edge(id, Cap{}, Cap{});
}
network.graph.change_edge(return_edge, Cap{}, Cap{});
Cap additional = network.graph.flow(source, sink);
return lower_bound_flow_result<Cap>{
initial + additional, recover_edge_flows(network)};
}
private:
struct built_network {
atcoder::mf_graph<Cap> graph;
int super_source;
int super_sink;
Cap total_demand{};
std::vector<int> original_edges;
std::vector<int> auxiliary_edges;
explicit built_network(int n)
: graph(n + 2), super_source(n), super_sink(n + 1) {}
};
built_network build_network() const {
built_network result(n);
std::vector<Cap> required_in(n);
std::vector<Cap> required_out(n);
result.original_edges.reserve(edges.size());
for (const edge ¤t : edges) {
result.original_edges.push_back(result.graph.add_edge(
current.from, current.to, current.upper - current.lower));
required_out[current.from] += current.lower;
required_in[current.to] += current.lower;
}
for (int vertex = 0; vertex < n; vertex++) {
if (required_in[vertex] > required_out[vertex]) {
Cap demand = required_in[vertex] - required_out[vertex];
result.auxiliary_edges.push_back(
result.graph.add_edge(result.super_source, vertex, demand));
result.total_demand += demand;
} else if (required_out[vertex] > required_in[vertex]) {
result.auxiliary_edges.push_back(result.graph.add_edge(
vertex, result.super_sink,
required_out[vertex] - required_in[vertex]));
}
}
return result;
}
static bool satisfy_demands(built_network &network) {
return network.graph.flow(network.super_source, network.super_sink) ==
network.total_demand;
}
std::vector<Cap> recover_edge_flows(built_network &network) const {
std::vector<Cap> result(edges.size());
for (int id = 0; id < int(edges.size()); id++) {
result[id] = edges[id].lower +
network.graph.get_edge(network.original_edges[id]).flow;
}
return result;
}
};
} // namespace noya