Shortest Successive Paths for solving Min-cost Max-flow

gistfile1.cpp

const int N = 1024;
bool vis[N];
double pot[N];
struct Edge {
  int a, b;
  double cost;
  int backward, forward;
  Edge(int a, int b, double cost, int cap) :a(a), b(b), cost(cost),
    backward(cap), forward(0) {}
  int other(int x) { return x == a ? b : a; }
  double cost_from(int x) { return x == a ? forward*cost : -backward*cost; }
  double red_cost_from(int x) {
    return (x==a?cost:-cost) - pot[x] + pot[other(x)];
  }
  int flow_from(int x) { return x == a ? forward : backward; }
  int cap_from(int x) { return x == a ? backward : forward; }
  void add_flow(int x, int flow) {
    if (x == a) {
      forward += flow;
      backward -= flow;
    } else {
      forward -= flow;
      backward += flow;
    }
  }
};

struct Node {
  int v, amt;
  Edge *pred;
  double d;
  Node() {}
  Node(int v, Edge* pred, int amt, double d) : v(v), pred(pred), amt(amt), d(d) {}
  bool operator<(const Node& o) const {
    return d > o.d;
  }
};

typedef list<Edge*> EdgeList;
typedef vector<EdgeList> AdjList;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
    it != adj[v].end(); ++it)

AdjList adj;
vector<Edge> edges;
double dists[N];
int amt[N]; // flow amount
Edge *preds[N];

// reduce costs using bellman-ford
bool reduce_bf(int s, int t, int n) {
  fill(dists, dists+n, -1);
  memset(amt, 0, sizeof(amt));
  memset(vis, 0, sizeof(vis));
  deque<int> q;
  q.push_back(s);
  dists[s] = 0;
  amt[s] = 1 << 29;
  preds[s] = NULL;
  while (q.size()) {
    int curr = q.front();
    q.pop_front();
    vis[curr] = false;
    FOR_EDGE(adj, curr, it) {
      Edge *e = *it;
      int o = e->other(curr);
      if (e->cap_from(curr) == 0) continue;
      if (dists[o] == -1 || dists[curr] + e->red_cost_from(curr) < dists[o]) {
        dists[o] = dists[curr] + e->red_cost_from(curr);
        amt[o] = min(amt[curr], e->cap_from(curr));
        preds[o] = e;
        if (!vis[o]) {
          vis[o] = true;
          q.push_back(o);
        }
      }
    }
  }
  if (amt[t] == 0) return false;
  // now reduce costs. assumption: graph is connected
  for (int i = 0; i < N; ++i) {
    pot[i] = -dists[i];
  }
  return true;
}


void flow(int t) {
  int curr = t;
  for (Edge *e = preds[t]; e != NULL; ) {
    int o = e->other(curr);
    e->add_flow(o, amt[t]);
    curr = o;
    e = preds[curr];
  }
}

// reduce costs using dijsktra's algorithm
bool reduce_dijkstra(int s, int t, int n) {
  fill(dists, dists+n, -1);
  memset(preds, 0, sizeof(preds));
  memset(amt, 0, sizeof(amt));
  priority_queue<Node> pq;
  pq.push(Node(s, NULL, 1 << 29, 0));
  while (pq.size()) {
    Node curr = pq.top();
    pq.pop();
    int v = curr.v;
    double d = curr.d;
    if (dists[v] != -1 && dists[v] < d) continue;
    dists[v] = d;
    preds[v] = curr.pred;
    amt[v] = curr.amt;
    if (v == t) break;
    FOR_EDGE(adj, v, it) {
      Edge *e = *it;
      if (e->cap_from(v) == 0) continue;
      int o = e->other(v);
      if (dists[o] == -1 || dists[o] > d + e->red_cost_from(v)) {
        pq.push(Node(o, e, min(amt[v], e->cap_from(v)),
              d + e->red_cost_from(v)));
      }
    }
  }
  if (dists[t] != -1) {
    for (int i = 0; i < N; ++i) {
      pot[i] -= dists[i] >= 0 ? dists[i] : dists[t];
    }
    return true;
  } else return false;
}
// shortest-sucessive-paths for min-cost-max-flow
void ssp(int s, int t, int n) {
  memset(pot, 0, sizeof(pot));
  reduce_bf(s, t, n); // not needed if costs are nonnegative
  flow(t);
  while (reduce_dijkstra(s, t, n)) flow(t);
}