Merevoli

Network flow (Dinitz)

Dec 4th, 2021
866
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int N = 1003,
  2.     oo = 0x3c3c3c3c;
  3. int n, m, S, T, d[N], c[N][N], f[N][N], Dfs[N], t = 0;
  4. vector < int > a[N];
  5. bool bfs(int S, int T) {
  6.     memset(d, 0, sizeof d);
  7.     queue < int > qu;
  8.     qu.push(S);
  9.     d[S] = 1;
  10.     while (qu.size()) {
  11.         int u = qu.front();
  12.         qu.pop();
  13.         if (u == T) return true;
  14.         for (int v: a[u])
  15.             if (!d[v] && f[u][v] < c[u][v]) {
  16.                 qu.push(v);
  17.                 d[v] = d[u] + 1;
  18.             }
  19.     }
  20.     return false;
  21. }
  22. int visit(int u, int Min) {
  23.     if (u == T) return Min;
  24.     if (Dfs[u] != t) Dfs[u] = t;
  25.     else return 0;
  26.     for (int v: a[u])
  27.         if (f[u][v] < c[u][v])
  28.             if (Dfs[v] != t && d[v] == d[u] + 1)
  29.                 if (int x = visit(v, min(Min, c[u][v] - f[u][v]))) {
  30.                     f[u][v] += x;
  31.                     f[v][u] -= x;
  32.                     return x;
  33.                 }
  34.     return 0;
  35. }
RAW Paste Data