CodeArchive MinCostMaxFlow

As used to get the 1st place on 10594.

int cap[N][N], flo[N][N], cost[N][N], vis[N], pot[N], par[N], dist[N], inf = 1000000000;

int mcf_update(int s, int t, ll &price){
  for(int i = 0; i < n; i++) dist[i] = inf, vis[i] = 0;
  dist[s] = 0;
  while(true){
    int best = inf, ind = -1;
    for(int i = 0; i < n; i++) if(!vis[i] && dist[i] < best) best = dist[ind = i];
    if(ind == -1) break; vis[ind] = 1;
    for(int i = 0; i < n; i++) if(!vis[i] && flo[ind][i] < cap[ind][i]){
      int pr = (flo[ind][i] >= 0 ? cost[ind][i] : -cost[ind][i]) + pot[ind] - pot[i];
      if(pr + dist[ind] < dist[i]) dist[i] = pr + dist[par[i] = ind];
    }
  }
  if(!vis[t]) return 0;
  for(int i = 0; i < n; i++) if(pot[i] < inf) pot[i] += dist[i];
  int mx = inf;
  for(int j = t, i = par[t]; j != s; j = i, i = par[i])
    mx <?= (flo[i][j] >= 0 ? (cap[i][j] - flo[i][j]) : -flo[i][j]);
  for(int j = t, i = par[t]; j != s; j = i, i = par[i])
    if(flo[i][j] >= 0) flo[i][j] += mx, flo[j][i] -= mx, price += (ll)cost[i][j]*mx;
    else  flo[i][j] += mx, flo[j][i] -= mx, price -= (ll)cost[i][j]*mx;
  return mx;
}

// usage
// int price = 0, change = 0;
// memset(pot, 0, sizeof(pot));
// do{ d -= change; } while(d && (change = mcf_update(0, n - 1, price)));

-- Main.YuryKholondyrev - 03 Mar 2006