m1une's library

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

View on GitHub

:heavy_check_mark: Max Flow
(graph/flow/max_flow.hpp)

Overview

MaxFlow<Cap> computes the maximum amount of flow that can be sent from a source vertex s to a sink vertex t in a directed capacitated graph.

The unlimited max_flow overload uses highest-label preflow-push. Active vertices are kept in flat buckets by height, so selecting a vertex of maximum height takes amortized constant time. The implementation also uses current-edge pointers, global relabeling, and the gap heuristic.

The limited-flow overload uses Dinic because preflow-push initially saturates the source edges and therefore does not naturally stop at an arbitrary flow limit. max_flow_push_relabel is an explicit alias for the unlimited highest-label implementation, while max_flow_dinic explicitly selects unlimited Dinic.

Graph Orientation

Directed flow network. An edge added by add_edge(from, to, cap) can send flow only from from to to.

For a bidirectional edge with one shared capacity, use add_undirected_edge(first, second, cap). It stores only two residual edges, half as many as two calls to add_edge. This is the intended interface for SPOJ FASTFLOW-style pipe networks.

The graph is stateful. Running max_flow changes residual capacities and stores the resulting flow. Use get_edge or edges after running it to inspect how much flow passed through each original edge.

How to Use It

Create MaxFlow<Cap> mf(n), add directed edges with capacities, and call mf.max_flow(s, t).

Capacities must be non-negative. add_undirected_edge requires a signed Cap; its residual capacity may reach 2 * cap, which must also fit Cap.

When the edge count is known, call reserve_edges(m) before adding edges. In addition to reserving edge metadata, it reserves adjacency capacity with some headroom above the average residual degree when the graph is dense enough for that to be useful. This avoids most small adjacency-list reallocations without allocating one buffer per vertex on extremely sparse graphs.

If every endpoint degree is already known, the overload reserve_edges(m, degrees) reserves exact adjacency capacities. Each original edge contributes one to each endpoint’s degree; a self-loop contributes two to its one endpoint. This overload is useful when edges are already stored in an input array, but the one-argument overload is usually nearly as fast.

You can call max_flow(s, t, flow_limit) when only up to flow_limit units are needed.

Edge Fields

Field Type Meaning
from int Original edge source.
to int Original edge destination.
cap Cap Original capacity currently assigned to this edge.
flow Cap Flow from from to to; it may be negative for an undirected edge.

Methods

Method Signature Description Complexity
Constructor MaxFlow() Creates an empty flow graph. $O(1)$
Constructor explicit MaxFlow(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 original edges. $O(1)$
reserve_edges void reserve_edges(int edge_count) Reserves edge metadata and adjacency capacity with average-degree headroom. $O(N + M)$ when reallocation occurs
reserve_edges void reserve_edges(int edge_count, const std::vector<int>& degrees) Reserves edge metadata and exact residual adjacency capacities. $O(N + M)$ when reallocation occurs
add_edge int add_edge(int from, int to, Cap cap) Adds a directed edge and returns its edge id. Amortized $O(1)$
add_undirected_edge int add_undirected_edge(int first, int second, Cap cap) Adds a bidirectional edge with shared capacity and returns its id. Amortized $O(1)$
get_edge Edge get_edge(int i) const Returns the current state of original edge i. $O(1)$
edges std::vector<Edge> edges() const Returns all original edges with current flow. $O(M)$
change_edge void change_edge(int i, Cap new_cap, Cap new_flow) Replaces edge i’s capacity and current flow; undirected flow may be negative. $O(1)$
max_flow Cap max_flow(int s, int t) Sends maximum flow from s to t with highest-label preflow-push. $O(N^2 \sqrt M)$
max_flow Cap max_flow(int s, int t, Cap flow_limit) Sends at most flow_limit additional flow. $O(N^2 M)$ in general; see below
max_flow_push_relabel Cap max_flow_push_relabel(int s, int t) Sends maximum additional flow with highest-label preflow-push. $O(N^2 \sqrt M)$
max_flow_dinic Cap max_flow_dinic(int s, int t) Sends maximum additional flow with Dinic. $O(N^2 M)$ in general; see below
min_cut std::vector<bool> min_cut(int s) const Returns vertices reachable from s in the residual graph. $O(N + M)$

Time Complexity of max_flow

Here, $N$ is the number of vertices and $M$ is the number of original edges. The residual graph stores two directed residual edges for each original edge, including an edge added by add_undirected_edge.

The unlimited overload and max_flow_push_relabel use highest-label preflow-push. The general worst-case bound is

\[O(N^2 \sqrt M).\]

This bound counts each Cap arithmetic or comparison operation as $O(1)$ and does not depend on the numerical size of the capacities.

max_flow_dinic and the flow_limit overload use pure Dinic. Each phase first uses BFS to construct a level graph in $O(N + M)$ time, then uses DFS with current-edge pointers to find a blocking flow. A blocking-flow computation takes $O(NM)$ time in the general case. After a blocking flow is found, the shortest residual distance from s to t strictly increases, so there are fewer than $N$ phases. This also gives the general bound $O(N^2M)$.

Bounds for Integer Capacities

When every capacity is an integer, several additional bounds hold for max_flow_dinic and the Dinic flow_limit overload. Let $u_e$ be the capacity of edge $e$, and define

\[\bar{u} = \frac{1}{M}\sum_e u_e, \qquad U = \max_e u_e,\]

and

\[\bar{c} = \frac{1}{N}\sum_v \min\left(\sum_{e\text{ enters }v}u_e, \sum_{e\text{ leaves }v}u_e\right).\]

If $F$ is the amount of flow still sendable from s to t in the current residual graph, the following are alternative upper bounds:

Condition Complexity
Integer capacities $O(FM)$
Average edge capacity $\bar{u}$ $O(\bar{u}M^{3/2})$
Maximum edge capacity $U$, with no parallel edges $O(UN^{2/3}M)$
Average vertex throughput $\bar{c}$ as defined above $O(\bar{c}\sqrt{N}M)$

These bounds hold at the same time as the general $O(N^2M)$ bound, so use the smallest applicable one. As usual, zero-capacity edges and isolated vertices can be omitted when applying the specialized bounds; if they are retained, include the $O(N+M)$ initialization and scanning cost.

The $O(FM)$ bound follows because each successful augmentation increases an integer flow by at least one. The other bounds combine this observation with a small residual cut after sufficiently many level-graph phases.

If every residual capacity at the start of a call has greatest common divisor $g$, divide the capacity-dependent quantities $F$, $\bar{u}$, $U$, and $\bar{c}$ by $g$ in these bounds. When using flow_limit, it must be scaled as well. Scaling all these values by $g$ does not change which paths and edges Dinic’s algorithm processes.

For unit-capacity graphs, $\bar{u}=U=1$. Combining the two edge-capacity bounds for the Dinic APIs gives the standard result

\[O\left(M \min\left(N^{2/3}, \sqrt{M}\right)\right).\]

On unit networks, where every non-terminal vertex has either one incoming edge or one outgoing edge, $\bar{c}=O(1)$ and the bound improves further to $O(M\sqrt{N})$. Bipartite matching networks are a common example.

For a detailed derivation of these bounds, see Dinic’s Algorithm and Its Time Complexity.

The flow_limit overload may stop before a complete maximum flow is found, so it can be faster in practice, but its general worst-case bound remains $O(N^2 M)$. With integer capacities, let $F_{call}$ be the amount returned by the call. Its flow-dependent work is $O(F_{call}M)$, and the exact bound including initialization and a final unsuccessful search is $O(N+(F_{call}+1)M)$. Here, $F_{call}$ is at most flow_limit. Every call returns only the additional flow sent during that call. Since the residual graph is preserved, calling max_flow again continues from the current flow rather than recomputing it from scratch.

Push-Relabel Alternative

max_flow_push_relabel(s, t) uses highest-label active-vertex selection, flat buckets, current-edge pointers, global relabeling, and the gap heuristic. Its general bound is $O(N^2 \sqrt M)$, including calls on a residual graph that already contains flow.

All maximum-flow methods return only the additional flow sent and leave a valid residual graph, so get_edge, edges, and min_cut behave the same afterward.

Minimum Cut

After running max flow, min_cut(s) returns the source side of a minimum s-t cut. An original edge crossing from cut[u] == true to cut[v] == false is saturated and belongs to some minimum cut boundary.

Example

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

int main() {
    m1une::flow::MaxFlow<long long> mf(4);
    mf.reserve_edges(5);
    mf.add_edge(0, 1, 2);
    mf.add_edge(0, 2, 1);
    mf.add_edge(1, 2, 1);
    mf.add_edge(1, 3, 1);
    mf.add_edge(2, 3, 2);

    std::cout << mf.max_flow(0, 3) << "\n";  // 3

    for (const auto& e : mf.edges()) {
        std::cout << e.from << " -> " << e.to << ": " << e.flow << "/" << e.cap << "\n";
    }
}

Required by

Verified with

Code

#ifndef M1UNE_FLOW_MAX_FLOW_HPP
#define M1UNE_FLOW_MAX_FLOW_HPP 1

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

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

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



#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

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
Back to top page