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.

🔗 Relacionados