Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- struct Edge {
- int u, v, f, c;
- };
- vector<Edge> e;
- vector<char> used;
- vector<vector<int>> g;
- int s, t;
- const int inf = 4e18;
- void add_edge(int u, int v, int c) {
- e.push_back({u, v, 0, c});
- e.push_back({v, u, 0, 0});
- g[u].push_back(e.size() - 2);
- g[v].push_back(e.size() - 1);
- }
- void add_undir_edge(int u, int v, int c) {
- e.push_back({u, v, 0, c});
- e.push_back({v, u, 0, c});
- g[u].push_back(e.size() - 2);
- g[v].push_back(e.size() - 1);
- }
- int dfs(int v, int minc) {
- if (v == t) return minc;
- if (used[v]) return 0;
- used[v] = true;
- random_shuffle(g[v].begin(), g[v].end());
- for (int i : g[v]) {
- if (e[i].f == e[i].c) continue;
- int res = dfs(e[i].v, min(minc, e[i].c - e[i].f));
- if (res) {
- e[i].f += res;
- e[i ^ 1].f -= res;
- return res;
- }
- }
- return 0;
- }
- void gen_gadget(int k) {
- int v = g.size();
- g.resize(v + 2 * k + 2, vector<int>());
- for (int i = 0; i < k; ++i) {
- add_undir_edge(v + i + 1, v + i, inf);
- add_undir_edge(v + i, v + 2 * k + 1, inf);
- }
- for (int i = k + 1; i <= 2 * k; ++i) {
- add_undir_edge(v + i - 1, v + i, inf);
- add_edge(v + i, v + i - k - 1, inf);
- }
- }
- pair<int, int> gen(int r, int k) { // {source, sink}
- if (r == -1) {
- g.resize(2);
- add_edge(0, 1, 1);
- return {0, 1};
- } else {
- pair<int, int> st = gen(r - 1, k);
- int s = g.size() + k;
- int s1 = g.size() + 2 * k + 1;
- int s2 = g.size() + 2 * k;
- gen_gadget(k);
- int up = g.size() + k;
- int up1 = g.size() + 2 * k + 1;
- int up2 = g.size() + 2 * k;
- gen_gadget(k);
- int out = g.size() + k;
- int out1 = g.size() + 2 * k + 1;
- int out2 = g.size() + 2 * k;
- gen_gadget(k);
- g.resize(g.size() + 1);
- int down = g.size() - 1;
- add_edge(s1, up, 1LL << r);
- add_edge(s2, down, 1LL << r);
- add_edge(up1, st.first, 1LL << r);
- add_edge(st.second, down, 1LL << r);
- add_edge(up2, out1, 1LL << r);
- add_edge(down, out2, 1LL << r);
- return {s, out};
- }
- }
- main() {
- srand(228);
- for (int k = 2; k < 30; ++k) {
- g.clear();
- e.clear();
- double before = clock() * 1.0 / CLOCKS_PER_SEC;
- pair<int, int> st = gen(k, k);
- s = st.first;
- t = st.second;
- int flow = 0;
- int iters = 0;
- while (true) {
- used.assign(g.size(), false);
- int res = dfs(s, inf);
- if (!res) {
- break;
- }
- flow += res;
- ++iters;
- }
- double after = clock() * 1.0 / CLOCKS_PER_SEC;
- cout << "Order of graph: " << k << ", vertices: " << g.size() << ", edges: "
- << e.size() / 2 << ", iterations: " << iters << ", time: " << after - before << ", max_flow: " << flow << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement