Advertisement
wrg0ababd

Untitled

Mar 23rd, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. struct Edge {
  7.     int u, v, f, c;
  8. };
  9.  
  10. vector<Edge> e;
  11. vector<char> used;
  12. vector<vector<int>> g;
  13. int s, t;
  14.  
  15. const int inf = 4e18;
  16.  
  17. void add_edge(int u, int v, int c) {
  18.     e.push_back({u, v, 0, c});
  19.     e.push_back({v, u, 0, 0});
  20.     g[u].push_back(e.size() - 2);
  21.     g[v].push_back(e.size() - 1);
  22. }
  23.  
  24. void add_undir_edge(int u, int v, int c) {
  25.     e.push_back({u, v, 0, c});
  26.     e.push_back({v, u, 0, c});
  27.     g[u].push_back(e.size() - 2);
  28.     g[v].push_back(e.size() - 1);
  29. }
  30.  
  31. int dfs(int v, int minc) {
  32.     if (v == t) return minc;
  33.     if (used[v]) return 0;
  34.     used[v] = true;
  35.     random_shuffle(g[v].begin(), g[v].end());
  36.     for (int i : g[v]) {
  37.         if (e[i].f == e[i].c) continue;
  38.         int res = dfs(e[i].v, min(minc, e[i].c - e[i].f));
  39.         if (res) {
  40.             e[i].f += res;
  41.             e[i ^ 1].f -= res;
  42.             return res;
  43.         }
  44.     }
  45.     return 0;
  46. }
  47.  
  48. void gen_gadget(int k) {
  49.     int v = g.size();
  50.     g.resize(v + 2 * k + 2, vector<int>());
  51.     for (int i = 0; i < k; ++i) {
  52.         add_undir_edge(v + i + 1, v + i, inf);
  53.         add_undir_edge(v + i, v + 2 * k + 1, inf);
  54.     }
  55.     for (int i = k + 1; i <= 2 * k; ++i) {
  56.         add_undir_edge(v + i - 1, v + i, inf);
  57.         add_edge(v + i, v + i - k - 1, inf);
  58.     }
  59. }
  60.  
  61. pair<int, int> gen(int r, int k) { // {source, sink}
  62.     if (r == -1) {
  63.         g.resize(2);
  64.         add_edge(0, 1, 1);
  65.         return {0, 1};
  66.     } else {
  67.         pair<int, int> st = gen(r - 1, k);
  68.         int s = g.size() + k;
  69.         int s1 = g.size() + 2 * k + 1;
  70.         int s2 = g.size() + 2 * k;
  71.         gen_gadget(k);
  72.         int up = g.size() + k;
  73.         int up1 = g.size() + 2 * k + 1;
  74.         int up2 = g.size() + 2 * k;
  75.         gen_gadget(k);
  76.         int out = g.size() + k;
  77.         int out1 = g.size() + 2 * k + 1;
  78.         int out2 = g.size() + 2 * k;
  79.         gen_gadget(k);
  80.         g.resize(g.size() + 1);
  81.         int down = g.size() - 1;
  82.         add_edge(s1, up, 1LL << r);
  83.         add_edge(s2, down, 1LL << r);
  84.         add_edge(up1, st.first, 1LL << r);
  85.         add_edge(st.second, down, 1LL << r);
  86.         add_edge(up2, out1, 1LL << r);
  87.         add_edge(down, out2, 1LL << r);
  88.         return {s, out};
  89.     }
  90. }
  91.  
  92.  
  93. main() {
  94.     srand(228);
  95.     for (int k = 2; k < 30; ++k) {
  96.         g.clear();
  97.         e.clear();
  98.         double before = clock() * 1.0 / CLOCKS_PER_SEC;
  99.         pair<int, int> st = gen(k, k);
  100.         s = st.first;
  101.         t = st.second;
  102.         int flow = 0;
  103.         int iters = 0;
  104.         while (true) {
  105.             used.assign(g.size(), false);
  106.             int res = dfs(s, inf);
  107.             if (!res) {
  108.                 break;
  109.             }
  110.             flow += res;
  111.             ++iters;
  112.         }
  113.         double after = clock() * 1.0 / CLOCKS_PER_SEC;
  114.         cout << "Order of graph: " << k << ", vertices: " << g.size() << ", edges: "
  115.              << e.size() / 2 << ", iterations: " << iters << ", time: " << after - before << ", max_flow: " << flow << endl;
  116.     }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement