CodeArchive MinCostMaxFlow

This works, there should be no negative edges in the beginning (I'll need to re-weight otherwise)

// assumes that the opposite edge has opposite cost make sure to understand that!!!
// watch for potential function overflow
const int N = 128;
const ll infll = 1ll << 50;
const int infint = 1 << 30;
int cost[N][N], cap[N][N], adj[N][N], flo[N][N], other[N][N], sz[N], par[N], vis[N], s;
ll pot[N], dist[N];

void add_edge(int a, int b, int c, int p){
  adj[a][sz[a]] = b, cost[a][sz[a]] =  p, cap[a][sz[a]] = c, flo[a][sz[a]] = 0, other[a][sz[a]] = sz[b];
  adj[b][sz[b]] = a, cost[b][sz[b]] = -p, cap[b][sz[b]] = 0, flo[b][sz[b]] = 0, other[b][sz[b]] = sz[a];
  sz[a]++, sz[b]++;
}

int mcf_update(int s, int t, ll &price, int n){
  for(int i = 0; i < n; i++) par[i] = -1, vis[i] = 0, dist[i] = infll; // init
  dist[s] = 0;
  // do dijkstra
  while(true){
    ll best = infll; int id = -1;
    for(int i = 0; i < n; i++) if(!vis[i] && dist[i] < best) best = dist[i], id = i;
    if(id == -1) break; vis[id] = 1;
    for(int i = 0; i < sz[id]; i++) 
      if(flo[id][i] < cap[id][i] && dist[id] + cost[id][i] + pot[id] - pot[adj[id][i]] < dist[adj[id][i]])
   dist[adj[id][i]] = dist[id] + cost[id][i] + pot[id] - pot[adj[id][i]], par[adj[id][i]] = other[id][i];
  }
  if(dist[t] >= infll) return 0; int mx = infint;
  for(int i = t; i != s; i = adj[i][par[i]]){
    int prev = adj[i][par[i]], id = other[i][par[i]];
    mx <?= (cap[prev][id] - flo[prev][id]);
  }
  for(int i = t; i != s; i = adj[i][par[i]]){
    int prev = adj[i][par[i]], id = other[i][par[i]];
    flo[prev][id] += mx; flo[i][par[i]] -= mx;
    price += cost[prev][id]*(ll)mx;
  }
  for(int i = 0; i < n; i++) if(pot[i] < infll) pot[i] += dist[i];
  return mx;
}

// usage:
//ll price = 0;
//memset(pot, 0, sizeof(pot));
//while(mcf_update(source, sink, price, sink + 1));

This works, definitely, even with negative edges:

// assumes that the opposite edge has opposite cost make sure to understand that!!!
const int N = 128;
const int inf = 1000000000;
int cost[N][N], cap[N][N], adj[N][N], flo[N][N], other[N][N], sz[N], par[N], dist[N], s;

void add_edge(int a, int b, int c, int p){
  adj[a][sz[a]] = b, cost[a][sz[a]] =  p, cap[a][sz[a]] = c, flo[a][sz[a]] = 0, other[a][sz[a]] = sz[b];
  adj[b][sz[b]] = a, cost[b][sz[b]] = -p, cap[b][sz[b]] = 0, flo[b][sz[b]] = 0, other[b][sz[b]] = sz[a];
  sz[a]++, sz[b]++;
}

int mcf_update(int s, int t, int &price, int n){
  for(int i = 0; i < n; i++) par[i] = -1, dist[i] = inf; // init
  dist[s] = 0;
  // do bellman-ford
  for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
      for(int j = 0; j < sz[i]; j++)
   if(flo[i][j] < cap[i][j] && dist[i] + cost[i][j] < dist[adj[i][j]])
     dist[adj[i][j]] = dist[i] + cost[i][j], par[adj[i][j]] = other[i][j];

  if(dist[t] >= inf) return 0; int mx = inf;
  for(int i = t; i != s; i = adj[i][par[i]]){
    int prev = adj[i][par[i]], id = other[i][par[i]];
    mx <?= (cap[prev][id] - flo[prev][id]);
  }
  for(int i = t; i != s; i = adj[i][par[i]]){
    int prev = adj[i][par[i]], id = other[i][par[i]];
    flo[prev][id] += mx; flo[i][par[i]] -= mx;
    price += cost[prev][id]*mx;
  }

  return mx;
}

// usage:
//int price = 0;
//while(mcf_update(source, sink, price, sink + 1));

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