m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Bounded Flow
(graph/flow/bounded_flow.hpp)

Overview

BoundedFlow<Cap> finds a feasible flow with lower and upper bounds on each edge. It also supports b-flow constraints by giving each vertex a required balance. BFlow<Cap> is an alias of BoundedFlow<Cap>.

For this library, vertex balance means:

outgoing_flow(v) - incoming_flow(v) = balance[v]

Positive balance is supply. Negative balance is demand.

Each edge may have any interval lower <= flow <= upper. The lower bound may be negative, so an edge can allow negative flow. For example, an edge u -> v with bounds [-3, 5] may carry -2, which behaves like sending 2 units from v to u.

Graph Orientation

Directed flow network. An edge added by add_edge(from, to, lower, upper) has the signed direction from -> to.

How It Works

The library reduces bounded flow to ordinary max flow.

For an edge u -> v with lower bound L and upper bound U, it sends L first and leaves residual capacity U - L. This changes the vertex balances, then a super source and super sink are added to check whether all remaining balance constraints can be satisfied.

How to Use It

Use add_edge(from, to, lower, upper) to add bounded directed edges.

Use these balance helpers for b-flow:

Then call feasible_flow(). It returns std::nullopt if no feasible flow exists.

For an exact s-t flow of value F, call feasible_st_flow(s, t, F). This adds temporary balances balance[s] += F and balance[t] -= F.

The result contains these members:

Member Type / Signature Meaning
edges std::vector<ResultEdge> Original edges with selected feasible flow.
balance std::vector<Cap> Vertex balances used for this solve.
get_edge ResultEdge get_edge(int i) const Returns result edge i.
flow Cap flow(int i) const Returns selected flow on edge i.

Edge Fields

Field Type Meaning
from int Edge source.
to int Edge destination.
lower Cap Lower bound on flow.
upper Cap Upper bound on flow.
flow Cap Present only in ResultEdge; selected feasible flow.

Methods

Method Signature Description Complexity
Constructor BoundedFlow() Creates an empty bounded-flow graph. $O(1)$
Constructor explicit BoundedFlow(int n) Creates a graph with n vertices. $O(N)$
size int size() const Returns the number of vertices. $O(1)$
edge_count int edge_count() const Returns the number of edges. $O(1)$
add_edge int add_edge(int from, int to, Cap lower, Cap upper) Adds an edge with bounds and returns its id. Amortized $O(1)$
get_edge Edge get_edge(int i) const Returns original edge i. $O(1)$
edges std::vector<Edge> edges() const Returns all original edges. $O(M)$
set_balance void set_balance(int v, Cap b) Sets balance[v] = b. $O(1)$
add_balance void add_balance(int v, Cap b) Adds signed balance to vertex v. $O(1)$
add_supply void add_supply(int v, Cap supply) Adds non-negative supply to vertex v. $O(1)$
add_demand void add_demand(int v, Cap demand) Adds non-negative demand to vertex v. $O(1)$
balance Cap balance(int v) const Returns balance[v]. $O(1)$
balances const std::vector<Cap>& balances() const Returns all balances. $O(1)$
feasible_flow std::optional<Result> feasible_flow() const Solves using stored balances. Max flow
feasible_flow std::optional<Result> feasible_flow(const std::vector<Cap>& balance) const Solves using explicit balances. Max flow
feasible_st_flow std::optional<Result> feasible_st_flow(int s, int t, Cap flow_value) const Solves exact s-t flow with value flow_value. Max flow

Alias

Alias Type
BFlow<Cap> BoundedFlow<Cap>

Example

#include "graph/flow/bounded_flow.hpp"
#include <iostream>

int main() {
    m1une::flow::BoundedFlow<long long> bf(3);
    int e0 = bf.add_edge(0, 1, 1, 3);
    int e1 = bf.add_edge(0, 2, 0, 2);
    int e2 = bf.add_edge(1, 2, -1, 2);  // negative flow is allowed

    bf.add_supply(0, 3);
    bf.add_demand(2, 3);

    auto res = bf.feasible_flow();
    if (!res) return 0;

    std::cout << res->flow(e0) << "\n";
    std::cout << res->flow(e1) << "\n";
    std::cout << res->flow(e2) << "\n";
}

Depends on

Required by

Verified with

Code

#ifndef M1UNE_FLOW_BOUNDED_FLOW_HPP
#define M1UNE_FLOW_BOUNDED_FLOW_HPP 1

#include <cassert>
#include <optional>
#include <vector>

#include "max_flow.hpp"

namespace m1une {
namespace flow {

template <class Cap>
struct BoundedFlow {
    struct Edge {
        int from;
        int to;
        Cap lower;
        Cap upper;
    };

    struct ResultEdge {
        int from;
        int to;
        Cap lower;
        Cap upper;
        Cap flow;
    };

    struct Result {
        std::vector<ResultEdge> edges;
        std::vector<Cap> balance;

        ResultEdge get_edge(int i) const {
            assert(0 <= i && i < int(edges.size()));
            return edges[i];
        }

        Cap flow(int i) const {
            assert(0 <= i && i < int(edges.size()));
            return edges[i].flow;
        }
    };

   private:
    int _n;
    std::vector<Edge> _edges;
    std::vector<Cap> _balance;

   public:
    BoundedFlow() : BoundedFlow(0) {}

    explicit BoundedFlow(int n) : _n(n), _balance(n, Cap(0)) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int edge_count() const {
        return int(_edges.size());
    }

    int add_edge(int from, int to, Cap lower, Cap upper) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(lower <= upper);
        int id = int(_edges.size());
        _edges.push_back(Edge{from, to, lower, upper});
        return id;
    }

    Edge get_edge(int i) const {
        assert(0 <= i && i < int(_edges.size()));
        return _edges[i];
    }

    std::vector<Edge> edges() const {
        return _edges;
    }

    void set_balance(int v, Cap b) {
        assert(0 <= v && v < _n);
        _balance[v] = b;
    }

    void add_balance(int v, Cap b) {
        assert(0 <= v && v < _n);
        _balance[v] += b;
    }

    void add_supply(int v, Cap supply) {
        assert(Cap(0) <= supply);
        add_balance(v, supply);
    }

    void add_demand(int v, Cap demand) {
        assert(Cap(0) <= demand);
        add_balance(v, -demand);
    }

    Cap balance(int v) const {
        assert(0 <= v && v < _n);
        return _balance[v];
    }

    const std::vector<Cap>& balances() const {
        return _balance;
    }

    std::optional<Result> feasible_flow() const {
        return feasible_flow(_balance);
    }

    std::optional<Result> feasible_flow(const std::vector<Cap>& balance) const {
        assert(int(balance.size()) == _n);
        int ss = _n, tt = _n + 1;
        MaxFlow<Cap> mf(_n + 2);
        std::vector<int> edge_ids;
        edge_ids.reserve(_edges.size());

        std::vector<Cap> need = balance;
        for (const auto& e : _edges) {
            edge_ids.push_back(mf.add_edge(e.from, e.to, e.upper - e.lower));
            need[e.from] -= e.lower;
            need[e.to] += e.lower;
        }

        Cap positive_sum = Cap(0), negative_sum = Cap(0);
        for (int v = 0; v < _n; v++) {
            if (need[v] > Cap(0)) {
                positive_sum += need[v];
                mf.add_edge(ss, v, need[v]);
            } else if (need[v] < Cap(0)) {
                negative_sum += -need[v];
                mf.add_edge(v, tt, -need[v]);
            }
        }
        if (positive_sum != negative_sum) return std::nullopt;
        if (mf.max_flow(ss, tt) != positive_sum) return std::nullopt;

        Result result;
        result.balance = balance;
        result.edges.reserve(_edges.size());
        for (int i = 0; i < int(_edges.size()); i++) {
            auto used = mf.get_edge(edge_ids[i]).flow;
            const auto& e = _edges[i];
            result.edges.push_back(ResultEdge{e.from, e.to, e.lower, e.upper, e.lower + used});
        }
        return result;
    }

    std::optional<Result> feasible_st_flow(int s, int t, Cap flow_value) const {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);
        std::vector<Cap> balance = _balance;
        balance[s] += flow_value;
        balance[t] -= flow_value;
        return feasible_flow(balance);
    }
};

template <class Cap>
using BFlow = BoundedFlow<Cap>;

}  // namespace flow
}  // namespace m1une

#endif  // M1UNE_FLOW_BOUNDED_FLOW_HPP
#line 1 "graph/flow/bounded_flow.hpp"



#include <cassert>
#include <optional>
#include <vector>

#line 1 "graph/flow/max_flow.hpp"



#include <algorithm>
#line 6 "graph/flow/max_flow.hpp"
#include <cstddef>
#include <limits>
#line 9 "graph/flow/max_flow.hpp"

namespace m1une {
namespace flow {

template <class Cap>
struct MaxFlow {
    struct Edge {
        int from;
        int to;
        Cap cap;
        Cap flow;
    };

   private:
    struct InternalEdge {
        int to;
        int rev;
        Cap cap;
    };

    struct Position {
        int from;
        int edge;
    };

    int _n;
    std::vector<Position> _pos;
    std::vector<std::vector<InternalEdge>> _g;

    Cap highest_label_preflow_push(int s, int t) {
        const int dead = 2 * _n;
        const int unreachable = _n + 1;
        std::vector<Cap> excess(_n, Cap(0));
        std::vector<int> state(8 * std::size_t(_n) + 2);
        int* height = state.data();
        int* height_count = height + _n;
        int* current = height_count + dead + 1;
        int* queue = current + _n;
        int* next = queue + _n;
        int* bucket_head = next + _n;
        std::vector<char> active(_n, false);
        int highest = -1;
        long long work = 0;
        const long long arc_count =
            2LL * static_cast<long long>(_pos.size());
        const long long work_limit = std::max(1LL, 4 * arc_count + _n);

        auto activate = [&](int v) {
            if (v == s || v == t || active[v] || excess[v] == Cap(0) ||
                height[v] >= dead) {
                return;
            }
            active[v] = true;
            next[v] = bucket_head[height[v]];
            bucket_head[height[v]] = v;
            highest = std::max(highest, height[v]);
        };

        auto rebuild_buckets = [&]() {
            std::fill(bucket_head, bucket_head + dead + 1, -1);
            std::fill(active.begin(), active.end(), false);
            highest = -1;
            for (int v = 0; v < _n; v++) activate(v);
        };

        auto global_relabel = [&]() {
            std::fill(height, height + _n, unreachable);
            std::fill(height_count, height_count + dead + 1, 0);
            std::fill(current, current + _n, 0);
            int head = 0;
            int tail = 0;
            height[t] = 0;
            height[s] = _n;
            queue[tail++] = t;
            while (head != tail) {
                int v = queue[head++];
                for (const auto& e : _g[v]) {
                    if (e.to == s || height[e.to] != unreachable) continue;
                    const auto& reverse = _g[e.to][e.rev];
                    if (reverse.cap == Cap(0)) continue;
                    height[e.to] = height[v] + 1;
                    queue[tail++] = e.to;
                }
            }
            for (int v = 0; v < _n; v++) height_count[height[v]]++;
            rebuild_buckets();
            work = 0;
        };

        auto gap = [&](int empty_height) {
            for (int v = 0; v < _n; v++) {
                if (v == s || v == t || height[v] <= empty_height ||
                    height[v] >= _n) {
                    continue;
                }
                height_count[height[v]]--;
                height[v] = unreachable;
                height_count[height[v]]++;
                current[v] = 0;
            }
            rebuild_buckets();
        };

        auto relabel = [&](int v) -> bool {
            int old_height = height[v];
            int new_height = dead;
            work += int(_g[v].size());
            for (const auto& e : _g[v]) {
                if (e.cap != Cap(0)) {
                    new_height = std::min(new_height, height[e.to] + 1);
                }
            }
            height_count[old_height]--;
            height[v] = std::min(new_height, dead);
            height_count[height[v]]++;
            current[v] = 0;
            if (old_height < _n && height_count[old_height] == 0) {
                gap(old_height);
                return true;
            }
            return false;
        };

        auto push = [&](int v, InternalEdge& e) {
            Cap sent = std::min(excess[v], e.cap);
            bool was_zero = excess[e.to] == Cap(0);
            e.cap -= sent;
            _g[e.to][e.rev].cap += sent;
            excess[v] -= sent;
            excess[e.to] += sent;
            if (was_zero) activate(e.to);
        };

        auto discharge = [&](int v) {
            while (excess[v] != Cap(0) && height[v] < dead) {
                if (current[v] == int(_g[v].size())) {
                    if (relabel(v)) return;
                    continue;
                }
                auto& e = _g[v][current[v]];
                work++;
                if (e.cap != Cap(0) && height[v] == height[e.to] + 1) {
                    push(v, e);
                } else {
                    current[v]++;
                }
            }
            activate(v);
        };

        for (auto& e : _g[s]) {
            if (e.to == s || e.cap == Cap(0)) continue;
            Cap sent = e.cap;
            e.cap = Cap(0);
            _g[e.to][e.rev].cap += sent;
            excess[e.to] += sent;
        }
        global_relabel();

        while (highest >= 0) {
            if (bucket_head[highest] == -1) {
                highest--;
                continue;
            }
            int v = bucket_head[highest];
            bucket_head[highest] = next[v];
            if (!active[v] || height[v] != highest) continue;
            active[v] = false;
            discharge(v);
            if (work >= work_limit) global_relabel();
        }
        return excess[t];
    }

   public:
    MaxFlow() : MaxFlow(0) {}

    explicit MaxFlow(int n) : _n(n), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int edge_count() const {
        return int(_pos.size());
    }

    void reserve_edges(int edge_count) {
        assert(0 <= edge_count);
        _pos.reserve(edge_count);
        if (_n == 0 || edge_count == 0 ||
            2 * std::size_t(edge_count) < std::size_t(_n)) {
            return;
        }
        const std::size_t average_degree =
            (3 * std::size_t(edge_count) + std::size_t(_n) - 1)
            / std::size_t(_n);
        for (auto& edges : _g) edges.reserve(average_degree);
    }

    void reserve_edges(int edge_count, const std::vector<int>& degrees) {
        assert(0 <= edge_count);
        assert(int(degrees.size()) == _n);
        _pos.reserve(edge_count);
        for (int v = 0; v < _n; v++) {
            assert(0 <= degrees[v]);
            _g[v].reserve(degrees[v]);
        }
    }

    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(Cap(0) <= cap);
        int id = int(_pos.size());
        int from_id = int(_g[from].size());
        int to_id = int(_g[to].size());
        if (from == to) to_id++;
        _pos.push_back(Position{from, from_id});
        _g[from].push_back(InternalEdge{to, to_id, cap});
        _g[to].push_back(InternalEdge{from, from_id, Cap(0)});
        return id;
    }

    int add_undirected_edge(int first, int second, Cap cap) {
        static_assert(std::numeric_limits<Cap>::is_signed);
        assert(0 <= first && first < _n);
        assert(0 <= second && second < _n);
        assert(Cap(0) <= cap);
        assert(cap <= std::numeric_limits<Cap>::max() / Cap(2));
        int id = int(_pos.size());
        int first_id = int(_g[first].size());
        int second_id = int(_g[second].size());
        if (first == second) second_id++;
        _pos.push_back(Position{first, ~first_id});
        _g[first].push_back(InternalEdge{second, second_id, cap});
        _g[second].push_back(InternalEdge{first, first_id, cap});
        return id;
    }

    Edge get_edge(int i) const {
        assert(0 <= i && i < int(_pos.size()));
        const auto& position = _pos[i];
        int from = position.from;
        bool undirected = position.edge < 0;
        int idx = undirected ? ~position.edge : position.edge;
        const auto& e = _g[from][idx];
        const auto& re = _g[e.to][e.rev];
        if (undirected) {
            return Edge{
                from,
                e.to,
                (e.cap + re.cap) / Cap(2),
                (re.cap - e.cap) / Cap(2)
            };
        }
        return Edge{from, e.to, e.cap + re.cap, re.cap};
    }

    std::vector<Edge> edges() const {
        std::vector<Edge> result;
        result.reserve(_pos.size());
        for (int i = 0; i < int(_pos.size()); i++) result.push_back(get_edge(i));
        return result;
    }

    void change_edge(int i, Cap new_cap, Cap new_flow) {
        assert(0 <= i && i < int(_pos.size()));
        assert(Cap(0) <= new_cap);
        auto& position = _pos[i];
        int from = position.from;
        bool undirected = position.edge < 0;
        int idx = undirected ? ~position.edge : position.edge;
        auto& e = _g[from][idx];
        auto& re = _g[e.to][e.rev];
        if (undirected) {
            assert(new_cap <= std::numeric_limits<Cap>::max() / Cap(2));
            assert(-new_cap <= new_flow && new_flow <= new_cap);
            e.cap = new_cap - new_flow;
            re.cap = new_cap + new_flow;
        } else {
            assert(Cap(0) <= new_flow && new_flow <= new_cap);
            e.cap = new_cap - new_flow;
            re.cap = new_flow;
        }
    }

    Cap max_flow(int s, int t) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);
        return highest_label_preflow_push(s, t);
    }

    Cap max_flow_push_relabel(int s, int t) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);
        return highest_label_preflow_push(s, t);
    }

    Cap max_flow_dinic(int s, int t) {
        return max_flow(s, t, std::numeric_limits<Cap>::max());
    }

    Cap max_flow(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        std::vector<int> work(3 * std::size_t(_n));
        int* level = work.data();
        int* iter = level + _n;
        int* queue = iter + _n;
        auto bfs = [&]() -> bool {
            std::fill(level, level + _n, -1);
            int head = 0;
            int tail = 0;
            level[s] = 0;
            queue[tail++] = s;
            while (head != tail) {
                int v = queue[head++];
                for (const auto& e : _g[v]) {
                    if (level[e.to] != -1 || e.cap == Cap(0)) continue;
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return true;
                    queue[tail++] = e.to;
                }
            }
            return level[t] != -1;
        };

        auto dfs = [&](auto&& self, int v, Cap up) -> Cap {
            if (v == s) return up;
            Cap result = Cap(0);
            const int current_level = level[v];
            auto& edges = _g[v];
            const int edge_count = int(edges.size());
            for (int& i = iter[v]; i < edge_count; i++) {
                auto& e = edges[i];
                if (level[e.to] + 1 != current_level) continue;
                auto& reverse = _g[e.to][e.rev];
                if (reverse.cap == Cap(0)) continue;
                Cap d = self(
                    self,
                    e.to,
                    std::min(up - result, reverse.cap)
                );
                if (d == Cap(0)) continue;
                e.cap += d;
                reverse.cap -= d;
                result += d;
                if (result == up) return result;
            }
            level[v] = _n;
            return result;
        };

        Cap flow = 0;
        while (flow < flow_limit && bfs()) {
            std::fill(iter, iter + _n, 0);
            flow += dfs(dfs, t, flow_limit - flow);
        }
        return flow;
    }

    std::vector<bool> min_cut(int s) const {
        assert(0 <= s && s < _n);
        std::vector<bool> visited(_n, false);
        std::vector<int> queue(_n);
        int head = 0;
        int tail = 0;
        visited[s] = true;
        queue[tail++] = s;
        while (head != tail) {
            int v = queue[head++];
            for (const auto& e : _g[v]) {
                if (e.cap == Cap(0) || visited[e.to]) continue;
                visited[e.to] = true;
                queue[tail++] = e.to;
            }
        }
        return visited;
    }
};

}  // namespace flow
}  // namespace m1une


#line 9 "graph/flow/bounded_flow.hpp"

namespace m1une {
namespace flow {

template <class Cap>
struct BoundedFlow {
    struct Edge {
        int from;
        int to;
        Cap lower;
        Cap upper;
    };

    struct ResultEdge {
        int from;
        int to;
        Cap lower;
        Cap upper;
        Cap flow;
    };

    struct Result {
        std::vector<ResultEdge> edges;
        std::vector<Cap> balance;

        ResultEdge get_edge(int i) const {
            assert(0 <= i && i < int(edges.size()));
            return edges[i];
        }

        Cap flow(int i) const {
            assert(0 <= i && i < int(edges.size()));
            return edges[i].flow;
        }
    };

   private:
    int _n;
    std::vector<Edge> _edges;
    std::vector<Cap> _balance;

   public:
    BoundedFlow() : BoundedFlow(0) {}

    explicit BoundedFlow(int n) : _n(n), _balance(n, Cap(0)) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int edge_count() const {
        return int(_edges.size());
    }

    int add_edge(int from, int to, Cap lower, Cap upper) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(lower <= upper);
        int id = int(_edges.size());
        _edges.push_back(Edge{from, to, lower, upper});
        return id;
    }

    Edge get_edge(int i) const {
        assert(0 <= i && i < int(_edges.size()));
        return _edges[i];
    }

    std::vector<Edge> edges() const {
        return _edges;
    }

    void set_balance(int v, Cap b) {
        assert(0 <= v && v < _n);
        _balance[v] = b;
    }

    void add_balance(int v, Cap b) {
        assert(0 <= v && v < _n);
        _balance[v] += b;
    }

    void add_supply(int v, Cap supply) {
        assert(Cap(0) <= supply);
        add_balance(v, supply);
    }

    void add_demand(int v, Cap demand) {
        assert(Cap(0) <= demand);
        add_balance(v, -demand);
    }

    Cap balance(int v) const {
        assert(0 <= v && v < _n);
        return _balance[v];
    }

    const std::vector<Cap>& balances() const {
        return _balance;
    }

    std::optional<Result> feasible_flow() const {
        return feasible_flow(_balance);
    }

    std::optional<Result> feasible_flow(const std::vector<Cap>& balance) const {
        assert(int(balance.size()) == _n);
        int ss = _n, tt = _n + 1;
        MaxFlow<Cap> mf(_n + 2);
        std::vector<int> edge_ids;
        edge_ids.reserve(_edges.size());

        std::vector<Cap> need = balance;
        for (const auto& e : _edges) {
            edge_ids.push_back(mf.add_edge(e.from, e.to, e.upper - e.lower));
            need[e.from] -= e.lower;
            need[e.to] += e.lower;
        }

        Cap positive_sum = Cap(0), negative_sum = Cap(0);
        for (int v = 0; v < _n; v++) {
            if (need[v] > Cap(0)) {
                positive_sum += need[v];
                mf.add_edge(ss, v, need[v]);
            } else if (need[v] < Cap(0)) {
                negative_sum += -need[v];
                mf.add_edge(v, tt, -need[v]);
            }
        }
        if (positive_sum != negative_sum) return std::nullopt;
        if (mf.max_flow(ss, tt) != positive_sum) return std::nullopt;

        Result result;
        result.balance = balance;
        result.edges.reserve(_edges.size());
        for (int i = 0; i < int(_edges.size()); i++) {
            auto used = mf.get_edge(edge_ids[i]).flow;
            const auto& e = _edges[i];
            result.edges.push_back(ResultEdge{e.from, e.to, e.lower, e.upper, e.lower + used});
        }
        return result;
    }

    std::optional<Result> feasible_st_flow(int s, int t, Cap flow_value) const {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);
        std::vector<Cap> balance = _balance;
        balance[s] += flow_value;
        balance[t] -= flow_value;
        return feasible_flow(balance);
    }
};

template <class Cap>
using BFlow = BoundedFlow<Cap>;

}  // namespace flow
}  // namespace m1une
Back to top page