Dinic worst case behavior

dinic_worst.cc

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

#include <vector>

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


#define rep4(i,s,n,x) for(std::common_type_t<decltype(s), decltype(n)> i=(s); i<(n); i+=(x))
#define rep3(i,s,n) rep4(i,s,n,1)
#define rep2(i,n) rep3(i,0,n)
#define repx(a,b,c,d,FUNC,...) FUNC
#define rep(...) repx(__VA_ARGS__, rep4, rep3, rep2)(__VA_ARGS__)

using F = long long int;
constexpr F INF = 1LL << 55;
using MF = atcoder::mf_graph<F>;

// 4p + 2k + 6 vertices
// k^2 + 4k + 6p + 2 edges
std::tuple<MF, std::size_t, std::size_t> build_graph(const std::size_t k, const std::size_t p) {
    std::size_t num_v = 0;
    auto add_v = [&]() -> auto { return num_v++; };
    auto add_vs = [&](const std::size_t k) -> auto {
        std::vector<std::size_t> res(k);
        for (auto &r : res) r = add_v();
        return res;
    };
    const auto U = add_vs(2*p + 1);
    const auto V = add_vs(2*p + 1);
    const auto A = add_vs(k);
    const auto B = add_vs(k);
    const auto Ai = add_v();
    const auto Ao = add_v();
    const auto Bi = add_v();
    const auto Bo = add_v();

    MF g(num_v);
    for (const auto &a : A) {
        g.add_edge(Ai, a, INF);
        g.add_edge(a, Ao, INF);
    }
    for (const auto &b : B) {
        g.add_edge(Bi, b, INF);
        g.add_edge(b, Bo, INF);
    }
    for (const auto &a : A) for (const auto &b : B) {
        g.add_edge(a, b, 1);
    }
    rep(i, std::size(U)-1) {
        g.add_edge(U[i], U[i+1], INF);
    }
    rep(i, std::size(V)-1) {
        g.add_edge(V[i+1], V[i], INF);
    }
    rep(i, 0, std::size(U), 4) {
        g.add_edge(U[i], Ai, (F) (k * k));
    }
    rep(i, 2, std::size(U), 4) {
        g.add_edge(U[i], Bi, (F) (k * k));
    }
    rep(i, 0, std::size(V), 4) {
        g.add_edge(Bo, V[i], (F) (k * k));
    }
    rep(i, 2, std::size(V), 4) {
        g.add_edge(Ao, V[i], (F) (k * k));
    }
    return std::make_tuple(g, U[0], V[0]);
}

#include <iostream>
#include <chrono>
int main() {
    using namespace std::chrono;
    using clock = high_resolution_clock;

    for (int i = 10; i < 100; i += 5) {
        const auto k = i;
        const auto p = i * i;
        std::cout << "(k, p) = (" << k << ", " << p << ")" << std::endl;
        auto [g, s, t] = build_graph(k, p);
        std::cout << "(n, m) = (" << g.min_cut(0).size() << ", " << g.edges().size() << ")" << std::endl;
        const auto start = clock::now();
        std::cout << g.flow(s, t) << std::endl;
        const auto stop = clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count() << " ms" << std::endl;
    }
    return 0;
}

output.txt

$ clang++ --std=c++17 ./dinic_worst.cc -O3
$ a
(k, p) = (10, 100)
(n, m) = (426, 742)
10100
27 ms
(k, p) = (15, 225)
(n, m) = (936, 1637)
50850
128 ms
(k, p) = (20, 400)
(n, m) = (1646, 2882)
160400
773 ms
(k, p) = (25, 625)
(n, m) = (2556, 4477)
391250
3280 ms
(k, p) = (30, 900)
(n, m) = (3666, 6422)
810900
11887 ms
(k, p) = (35, 1225)
(n, m) = (4976, 8717)
^C
[2]    1345380 interrupt  ./a.out
./a.out  17.89s user 0.04s system 99% cpu 18.013 total

The generator takes 2 arguments, k and p, and outputs a network consists of 4p + 2k + 6 vertices and k^2 + 4k + 6p + 2 edges.
Dinic's algorithm on this graph will need Θ(p) phases, each phase need Θ(k^2) flow augmentations, where augmentations on i-th phase takes Θ(i) time. So Dinic's algorithm takes Θ(k^2 p^2) time on this network.
Given a limit for the number of nodes n and the number of edges m, you may want to choose k and p so that k = Θ(min(n, √m)) and p = Θ(min(n, m)).

This generator is based on Fig. 1 of this article, with slight modifications;

• s and t are now combined with u and v respectively,
• S and T are called A and B,
• To reduce the number of edges, 4 additional nodes Ai, Ao, Bi, Bo (i/o stands for in/out) are introduces. Edges between U/V and A/B now pass through one of these 4 nodes. With this modification, Θ(kp) part in the number of edges is reduced to Θ(k+p).