Advertisement
Guest User

Untitled

a guest
Aug 24th, 2021
529
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. struct NetworkSimplex {
  2.   struct Edge { int a, b, c, k, f = 0; };
  3.  
  4.   int n;
  5.   vector<int> pei, depth, dual;
  6.   vector<Edge> E;
  7.   vector<set<int>> tree;
  8.  
  9.   NetworkSimplex(int n) :
  10.     n(n), pei(n + 1, -1), depth(n + 1, 0),
  11.     dual(n + 1, 0), tree(n + 1) {}
  12.  
  13.   int AddEdge(int a, int b, int c, int k) {
  14.     E.push_back({a, b, c, k});
  15.     E.push_back({b, a, 0, -k});
  16.     return E.size() - 2;
  17.   }
  18.   void dfs(int node) {
  19.     for (auto ei : tree[node]) {
  20.       if (ei == pei[node]) continue;
  21.       int vec = E[ei].b;
  22.       dual[vec] = dual[node] + E[ei].k;
  23.       pei[vec] = (ei ^ 1);
  24.       depth[vec] = 1 + depth[node];
  25.       dfs(vec);
  26.     }
  27.   }
  28.   template<typename CB>
  29.   void walk(int ei, CB&& cb) {
  30.     cb(ei);
  31.     int a = E[ei].a, b = E[ei].b;
  32.     while (a != b) {
  33.       if (depth[a] > depth[b])
  34.         cb(pei[a]^1), a = E[pei[a]].b;
  35.       else
  36.         cb(pei[b]), b = E[pei[b]].b;
  37.     }
  38.   }
  39.   long long Compute() {
  40.     for (int i = 0; i < n; ++i) {
  41.       int ei = AddEdge(n, i, 0, 0);
  42.       tree[n].insert(ei);
  43.       tree[i].insert(ei^1);
  44.     }  
  45.    
  46.     long long answer = 0;
  47.     int flow, cost, ein, eout, ptr = 0;
  48.     const int B = 3 * n;
  49.     for (int z = 0; z < E.size() / B + 1; ++z) {
  50.       // Initialize tree tables.
  51.       if (!z) dfs(n);
  52.       // Find negative cycle (round-robin).
  53.       pair<int, int> pin = {0, -1};
  54.       for (int t = 0; t < B; ++t, (++ptr) %= E.size()) {
  55.         auto& e = E[ptr];
  56.         if (e.f < e.c)
  57.           pin = min(pin, make_pair(
  58.               dual[e.a] + e.k - dual[e.b], ptr));
  59.       }
  60.       tie(cost, ein) = pin;
  61.       if (cost == 0) continue;
  62.       // Pivot around ein.
  63.       pair<int, int> pout = {E[ein].c - E[ein].f, ein};
  64.       walk(ein, [&](int ei) {
  65.         pout = min(pout, make_pair(E[ei].c - E[ei].f, ei));
  66.       });
  67.       tie(flow, eout) = pout;
  68.       walk(ein, [&](int ei) {
  69.         E[ei].f += flow, E[ei^1].f -= flow;
  70.       });
  71.       tree[E[ein].a].insert(ein);
  72.       tree[E[ein].b].insert(ein^1);
  73.       tree[E[eout].a].erase(eout);
  74.       tree[E[eout].b].erase(eout^1);
  75.       // Update answer.
  76.       answer += 1LL * flow * cost;
  77.       z = -1;
  78.     }
  79.     return answer;
  80.   }
  81. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement