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; } } } };