Exponential instance for a wrong implementation of Dinic

gen.cpp

#include <iostream>
#include <vector>
#include <tuple>
#include <array>

// s        u - u - u - u
// |  > a <   X   X   X    > c - t
// b        v - v - v - v


const size_t n = 100;

int main() {
    std::vector<std::tuple<size_t, size_t, int32_t>> edges;
    const size_t s = 0;
    const size_t a = 1;
    const size_t b = 2;
    const size_t c = 3;
    const size_t t = 4;
    std::array<size_t, 2> uv = { 5, 6 };

    edges.emplace_back(s, a, 1);
    edges.emplace_back(s, b, 2);
    edges.emplace_back(b, a, 2);
    edges.emplace_back(c, t, 2);
    for (const auto &x : uv) {
        edges.emplace_back(a, x, 3);
    }
    while (true) {
        std::array<size_t, 2> next_uv = { uv[0] + 2, uv[1] + 2 };
        if (next_uv[1] >= n) {
            break;
        }
        for (const auto &x : uv) {
            for (const auto &y : next_uv) {
                edges.emplace_back(x, y, 3);
            }
        }
        std::swap(uv, next_uv);
    }
    for (const auto &x : uv) {
        edges.emplace_back(x, c, 3);
    }

    std::cout << n << ' ' << edges.size() << std::endl;
    std::cout << s << ' ' << t << std::endl;
    for (const auto &[x, y, c] : edges) {
        std::cout << x << ' ' << y << ' ' << c << std::endl;
    }
    return 0;
}

input.txt

100 192
0 4
0 1 1
0 2 2
2 1 2
3 4 2
1 5 3
1 6 3
5 7 3
5 8 3
6 7 3
6 8 3
7 9 3
7 10 3
8 9 3
8 10 3
9 11 3
9 12 3
10 11 3
10 12 3
11 13 3
11 14 3
12 13 3
12 14 3
13 15 3
13 16 3
14 15 3
14 16 3
15 17 3
15 18 3
16 17 3
16 18 3
17 19 3
17 20 3
18 19 3
18 20 3
19 21 3
19 22 3
20 21 3
20 22 3
21 23 3
21 24 3
22 23 3
22 24 3
23 25 3
23 26 3
24 25 3
24 26 3
25 27 3
25 28 3
26 27 3
26 28 3
27 29 3
27 30 3
28 29 3
28 30 3
29 31 3
29 32 3
30 31 3
30 32 3
31 33 3
31 34 3
32 33 3
32 34 3
33 35 3
33 36 3
34 35 3
34 36 3
35 37 3
35 38 3
36 37 3
36 38 3
37 39 3
37 40 3
38 39 3
38 40 3
39 41 3
39 42 3
40 41 3
40 42 3
41 43 3
41 44 3
42 43 3
42 44 3
43 45 3
43 46 3
44 45 3
44 46 3
45 47 3
45 48 3
46 47 3
46 48 3
47 49 3
47 50 3
48 49 3
48 50 3
49 51 3
49 52 3
50 51 3
50 52 3
51 53 3
51 54 3
52 53 3
52 54 3
53 55 3
53 56 3
54 55 3
54 56 3
55 57 3
55 58 3
56 57 3
56 58 3
57 59 3
57 60 3
58 59 3
58 60 3
59 61 3
59 62 3
60 61 3
60 62 3
61 63 3
61 64 3
62 63 3
62 64 3
63 65 3
63 66 3
64 65 3
64 66 3
65 67 3
65 68 3
66 67 3
66 68 3
67 69 3
67 70 3
68 69 3
68 70 3
69 71 3
69 72 3
70 71 3
70 72 3
71 73 3
71 74 3
72 73 3
72 74 3
73 75 3
73 76 3
74 75 3
74 76 3
75 77 3
75 78 3
76 77 3
76 78 3
77 79 3
77 80 3
78 79 3
78 80 3
79 81 3
79 82 3
80 81 3
80 82 3
81 83 3
81 84 3
82 83 3
82 84 3
83 85 3
83 86 3
84 85 3
84 86 3
85 87 3
85 88 3
86 87 3
86 88 3
87 89 3
87 90 3
88 89 3
88 90 3
89 91 3
89 92 3
90 91 3
90 92 3
91 93 3
91 94 3
92 93 3
92 94 3
93 95 3
93 96 3
94 95 3
94 96 3
95 97 3
95 98 3
96 97 3
96 98 3
97 3 3
98 3 3

wrong_dinic.cpp

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

template<typename F, bool BFS_FORWARD, bool DFS_FORWARD> struct Dinic {
    struct E {
        size_t to, rev;
        F flow, cap;
    };

    Dinic(const size_t n) : n(n), g(n) {
    }
    void add_edge(const size_t &u, const size_t &v, const F cap) {
        const size_t e = g[u].size();
        const size_t re = g[v].size() + (u == v);
        g[u].emplace_back(E{v, re, 0, cap});
        g[v].emplace_back(E{u, e, 0, 0});
    }

    bool bfs_forward(const size_t &s, const size_t &t) {
        label.assign(n, n);
        q.clear();
        q.push_back(s);
        label[s] = 0;
        for (size_t pos = 0; pos < q.size(); ++pos) {
            const size_t u = q[pos];
            for (const auto &e : g[u]) {
                if (e.flow >= e.cap || label[e.to] < n) {
                    continue;
                }
                label[e.to] = label[u] + 1;
                q.push_back(e.to);
            }
        }
        return label[t] < n;
    }

    bool bfs_backward(const size_t &s, const size_t &t) {
        label.assign(n, 0);
        q.clear();
        q.push_back(t);
        label[t] = n;
        for (size_t pos = 0; pos < q.size(); ++pos) {
            const size_t u = q[pos];
            for (const auto &e : g[u]) {
                const auto &re = g[e.to][e.rev];
                if (re.flow >= re.cap || label[e.to] > 0) {
                    continue;
                }
                label[e.to] = label[u] - 1;
                q.push_back(e.to);
            }
        }
        return label[s] > 0;
    }

    F dfs_forward(const size_t &u, const size_t &t, const F limit) {
        if (u == t) {
            return limit;
        }
        F so_far = 0;
        // BUG: Missing important `&` here!!
        for (size_t /* & */ i = current_edge[u]; i < g[u].size(); ++i) {
            auto &e = g[u][i];
            if (e.flow >= e.cap || label[e.to] <= label[u]) {
                continue;
            }
            F f = dfs_forward(e.to, t, std::min(limit - so_far, e.cap - e.flow));
            if (f == 0) {
                continue;
            }
            auto &re = g[e.to][e.rev];
            e.flow += f;
            re.flow -= f;
            so_far += f;
            if (so_far == limit) {
                break;
            }
        }
        return so_far;
    }
    F dfs_backward(const size_t &s, const size_t &u, const F limit) {
        if (u == s) {
            return limit;
        }
        F so_far = 0;
        // BUG: Missing important `&` here!!
        for (size_t /* & */ i = current_edge[u]; i < g[u].size(); ++i) {
            auto &e = g[u][i];
            auto &re = g[e.to][e.rev];
            if (re.flow >= re.cap || label[e.to] >= label[u]) {
                continue;
            }
            F f = dfs_backward(s, e.to, std::min(limit - so_far, re.cap - re.flow));
            if (f == 0) {
                continue;
            }
            e.flow -= f;
            re.flow += f;
            so_far += f;
            if (so_far == limit) {
                break;
            }
        }
        return so_far;
    }

    F solve(const size_t &s, const size_t &t) {
        F res = 0;
        while (BFS_FORWARD ? bfs_forward(s, t) : bfs_backward(s, t)) {
            current_edge.assign(n, 0);
            res += DFS_FORWARD ? dfs_forward(s, t, std::numeric_limits<F>::max()) : dfs_backward(s, t, std::numeric_limits<F>::max());
        }
        return res;
    }

    private:
    size_t n;
    std::vector<std::vector<E>> g;
    std::vector<size_t> label; // s: lower, t: higher
    std::vector<size_t> q;
    std::vector<size_t> current_edge;
};

int main() {
    using namespace std;
    size_t n, m, s, t;
    cin >> n >> m >> s >> t;
    Dinic<int, true, true> g(n);
    // Dinic<int, true, false> g(n);
    // Dinic<int, false, true> g(n);
    // Dinic<int, false, false> g(n);
    for (int i = 0; i < m; ++i) {
        size_t u, v; int c;
        cin >> u >> v >> c;
        g.add_edge(u, v, c);
    }
    cout << g.solve(s, t) << endl;
    return 0;
}

Licensed under NYSL, you can do whatever.

Though it would be grateful if you could report issues here, if you found any :)