Merevoli

Network flow (Edmonds Karp basic)

Dec 4th, 2021
1,046
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int n, m, source, target;
  2. vector < int > a[12309];
  3. long c[2309][2309], f[2309][2309], d[12309];
  4. const long oo = 1000111000111000;
  5. void minimize(long & a, long b) {
  6.     if (a > b) a = b;
  7. }
  8. bool findpath(int start, int target) {
  9.     queue < int > qu;
  10.     int i, u, v;
  11.     for (i = 1; i <= n; i++) d[i] = 0;
  12.     d[start] = oo;
  13.     qu.push(start);
  14.     while (qu.size()) {
  15.         u = qu.front();
  16.         qu.pop();
  17.         if (u == target) return true;
  18.         for (i = 0; v = a[u][i]; i++)
  19.             if (d[v] == 0 && c[u][v] > f[u][v]) {
  20.                 d[v] = u;
  21.                 qu.push(v);
  22.             }
  23.     }
  24.     return false;
  25. }
  26. void enlarge() {
  27.     long u, v, delta = oo;
  28.     for (v = target;
  29.         (u = d[v]) != oo; v = u) minimize(delta, c[u][v] - f[u][v]);
  30.     for (v = target; v != source; v = u) {
  31.         u = d[v];
  32.         f[u][v] += delta;
  33.         f[v][u] -= delta;
  34.     }
  35. }
  36. long answer(int u) {
  37.     int i, v;
  38.     long r = 0;
  39.     for (i = 0; v = a[u][i]; i++) r += f[u][v];
  40.     return r;
  41. }
RAW Paste Data