Skip to content

Instantly share code, notes, and snippets.

@Vicfred
Forked from MiSawa/gen.cpp
Created September 10, 2020 08:52
Show Gist options
  • Save Vicfred/0f50eb5ebfdc979773f7e608b2ca9c26 to your computer and use it in GitHub Desktop.
Save Vicfred/0f50eb5ebfdc979773f7e608b2ca9c26 to your computer and use it in GitHub Desktop.
Exponential instance for a wrong implementation of Dinic
#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;
}
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
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment