CodeArchive MaximumFlowShort

Maximum Flow Short Version

This code uses dfs to find path. It is a simple Ford Fulkerson Algorithm. A longer, but generally better way of Maximum Flow is the Edmond-Karp Algorithm.

int dfs(int now, int goal, int mx){ // max flow
  if(now == goal) return mx; vis[now] = 1; int temp;
  for(int i = 0; i < n + 2; i++) if(!vis[i] && flo[now][i] < cap[now][i])
    if((temp = dfs(i, goal, mx <? (cap[now][i] - flo[now][i]))))
      { flo[now][i] += temp, flo[i][now] -= temp; return temp; }
  return 0;
}
// do{ memset(vis, 0, sizeof(vis)); } while(dfs(n, n + 1, 2000000000));

BFS version, a little bit faster...

int cap[N][N], adj[N][N], asz[N], q[N], t, n, d, m, u, v, c, p, e, test = 1;  
int vis[N];

int bfs(int now, int goal){
  int f = 0, b = 0, x; q[b++] = now;
  memset(vis, -1, sizeof(vis));
  while(b > f && vis[goal] == -1){
    x = q[f++];
    for(int i = 0, k = adj[x][0]; i < asz[x]; k = adj[x][++i])
      if(vis[k] == -1 && cap[x][k] > 0) vis[k] = x, q[b++] = k;
  } if(vis[goal] == -1) return 0;
  int mn = 2000000000;
  for(int p = goal; p != now; p = vis[p]) mn <?= cap[vis[p]][p];
  for(int p = goal; p != now; p = vis[p]) cap[vis[p]][p] -= mn, cap[p][vis[p]] += mn;
  return mn;
}

-- Main.YuryKholondyrev - 18 Nov 2005