Flujo máximo (Ford-Fulkerson)
Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Flujo máximo entre fuente y sumidero buscando caminos aumentantes por BFS (Edmonds-Karp) sobre la red residual; da también el corte mínimo.
Complejidad: O(V·E²) (Edmonds-Karp).
Cuándo usarlo
Modelar problemas como flujo: emparejamientos, cortes, selección con restricciones. La dualidad flujo-máximo = corte-mínimo es clave.
Implementación recomendada (C++)
struct MaxFlow { // Edmonds-Karp con matriz de capacidades
int n; vector<vector<long long>> cap; vector<vector<int>> g;
MaxFlow(int n) : n(n), cap(n, vector<long long>(n, 0)), g(n) {}
void add(int u, int v, long long c) {
if (!cap[u][v] && !cap[v][u]) { g[u].push_back(v); g[v].push_back(u); }
cap[u][v] += c;
}
long long maxflow(int s, int t) {
long long flow = 0;
while (true) {
vector<int> par(n, -1); par[s] = s;
queue<int> q; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) if (par[v] == -1 && cap[u][v] > 0) { par[v] = u; q.push(v); }
}
if (par[t] == -1) break;
long long aug = LLONG_MAX;
for (int v = t; v != s; v = par[v]) aug = min(aug, cap[par[v]][v]);
for (int v = t; v != s; v = par[v]) {
cap[par[v]][v] -= aug;
cap[v][par[v]] += aug; // arista de retorno: permite deshacer flujo después
}
flow += aug;
}
return flow;
}
};⚠️ Notas
El corte mínimo sale gratis al terminar: son los nodos alcanzables desde s por aristas con capacidad restante > 0 (las aristas que salen de ese conjunto forman el corte). Ojo con la memoria: la matriz de capacidades es O(V²), así que esta versión sirve hasta unos pocos miles de nodos. Dinic, flujos más eficientes y el min-cost flow están fuera del syllabus.