DinicとEdmondsKarp

どれが最新か分からなくなりそうなのでここにメモ。

// UVA 10989 AC:0.990sec
// PKU 3469 AC:5938MS
// (時間はdinicの方)
class Graph {
private:
  struct Edge {
    int to, back, flow, cap;
    Edge(int to, int cap, int back) : to(to), back(back), flow(0), cap(cap) {}
    int residue() { return cap - flow; }
  };
  int n;
  vector<vector<Edge> > g;
public:
  Graph(int n) : n(n), g(n) {}
  void insert(int i, int j, int c) {
    g[i].push_back(Edge(j, c, g[j].size()));
    //g[j].push_back(Edge(i, 0, g[i].size() - 1)); // 1) directed graph
    g[j].push_back(Edge(i, c, g[i].size() - 1)); // 2) undirected graph
  }
  int dinic(int s, int t) {
    for (int flow = 0, P[n], Q[n];;) {
      memset(P, -1, sizeof(P));
      int QF = 0, QB = 0;
      P[Q[QB++] = s] = -2;
      while (QB > QF && P[t] == -1)
        for (int u = Q[QF++], v, i = 0; i < g[u].size(); ++i)
          if (P[v = g[u][i].to] == -1 && g[u][i].residue() > 0)
            P[Q[QB++] = v] = g[u][i].back;
      if (P[t] == -1) return flow;
      for (int i = 0, z; i < g[t].size(); ++i)
        if (g[z = g[t][i].to][g[t][i].back].residue() > 0 && P[z] != -1) {
          int inc = g[z][g[t][i].back].residue();
          for (int e = z; P[e] >= 0; e = g[e][P[e]].to)
            inc = min(inc, g[g[e][P[e]].to][g[e][P[e]].back].residue());
          if (!inc) continue;
          g[t][i].flow -= inc, g[z][g[t][i].back].flow += inc;
          for (int e = z; P[e] >= 0; e = g[e][P[e]].to)
            g[e][P[e]].flow -= inc, g[g[e][P[e]].to][g[e][P[e]].back].flow += inc;
          flow += inc;
        }
    }
  }
  int edmondsKarp(int s, int t) {
    for (int flow = 0, P[n], Q[n];;) {
      memset(P, -1, sizeof(P));
      int QF = 0, QB = 0;
      P[Q[QB++] = s] = -2;
      while (QB > QF && P[t] == -1)
        for (int u = Q[QF++], v, i = 0; i < g[u].size(); ++i)
          if (P[v = g[u][i].to] == -1 && g[u][i].residue() > 0)
            P[Q[QB++] = v] = g[u][i].back;
      if (P[t] == -1) return flow;
      int inc = INT_MAX;
      for (int e = t; P[e] != -2; e = g[e][P[e]].to)
        inc = min(inc, g[g[e][P[e]].to][g[e][P[e]].back].residue());
      for (int e = t; P[e] != -2; e = g[e][P[e]].to)
        g[e][P[e]].flow -= inc, g[g[e][P[e]].to][g[e][P[e]].back].flow += inc;
      flow += inc;
    }
  }
};

2009/7/10追記。Dinic書き直し。

// SPOJ 4110 AC: 2.6sec
// UVA 10989 AC: 0.692sec

#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<typename T>
struct Graph {
  struct Edge {
    int to, back;
    T flow, cap;
    Edge(int to, T cap, int back) : to(to), back(back), flow(0), cap(cap) {}
    T Residue() { return cap - flow; }
  };
  int n;
  vector<vector<Edge> > edges;
  Graph(int n) : n(n), edges(n) {}
  void Connect(int i, int j, T c) {
    edges[i].push_back(Edge(j, c, edges[j].size()));
    //edges[j].push_back(Edge(i, 0, edges[i].size() - 1)); // 1) directed graph
    edges[j].push_back(Edge(i, c, edges[i].size() - 1)); // 2) undirected graph
  }
  Edge& Back(Edge& e) { return edges[e.to][e.back]; }
  T Dinic(int s, int t) {
    int P[n], Q[n], QF, QB;
    for (T flow = 0;;) {
      memset(P, -1, sizeof(P));
      for (QF = QB = 0, P[Q[QB++] = s] = -2; QB > QF && P[t] == -1;) {
        int u = Q[QF++];
        FOR(e, edges[u]) if (P[e->to] == -1 && e->Residue() > 0)
          P[e->to] = e->back, Q[QB++] = e->to;
      }
      if (P[t] == -1) return flow;
      FOR(e, edges[t]) if (Back(*e).Residue() > 0 && P[e->to] != -1) {
        T inc = Back(*e).Residue();
        for (int u = e->to; P[u] >= 0; u = edges[u][P[u]].to)
          inc = min(inc, Back(edges[u][P[u]]).Residue());
        if (inc == 0) continue;
        e->flow -= inc, Back(*e).flow += inc;
        for (int u = e->to; P[u] >= 0; u = edges[u][P[u]].to)
          edges[u][P[u]].flow -= inc, Back(edges[u][P[u]]).flow += inc;
        flow += inc;
      }
    }
  }
};