【代码存档】Edmonds Karp算法

[cpp]
#include
#include
using std::min;

const int INF = 0x7ffffff;
int v, e, pre[205], inc[205], queue[205], g[205][205], f[205][205];

bool bfs(int src, int des) {
int fp = 0, rp = 0;
for (int i = 1; i <= v; ++ i) { pre[i] = -1; } queue[fp] = src; inc[src] = INF; while (fp <= rp) { int u = queue[fp ++]; for (int i = 1; i <= v; ++ i) { if ((pre[i] == -1) && (f[u][i] < g[u][i])) { inc[i] = min(inc[u], g[u][i] - f[u][i]); pre[i] = u; if (i == des) { return true; } queue[++ rp] = i; } } } return false; } int Edmonds_Karp(int src, int des) { int maxFlow = 0; while (bfs(src, des)) { maxFlow += inc[des]; for (int i = des; i != src; i = pre[i]) { f[pre[i]][i] += inc[des]; f[i][pre[i]] = -f[pre[i]][i]; } } return maxFlow; } int main(void) { scanf("%d %d", &e, &v); for (int i = 1; i <= e; ++ i) { int x, y, k; scanf("%d %d %d", &x, &y, &k); g[x][y] += k; } printf("%d\n", Edmonds_Karp(1, v)); return 0; } [/cpp]