Flujo máximo
Edmonds-Karp (EK)
Complejidad: \\(\\mathcal{O}(nm^2)\\). Adecuado para grafos con \\(n \\leq 10^3\\) a \\(10^4\\) nodos.
El método consiste en buscar repetidamente caminos aumentantes desde el origen hasta el destino mediante BFS. Se identifica la capacidad residual mínima \\(x\\) a lo largo del camino y se reduce cada arista en \\(x\\). El proceso se detiene cuando ya no existe ningún camino aumentante.
Para permitir la cancelación de decisiones previas, se agregan aristas inversas con capacidad inicial cero. Cada vez que una arista directa pierde capacdiad, su arista inversa la gana.
// Flujo máximo con Edmonds-Karp
const int MAXN = 210, MAXM = 5010;
const long long INF_CAP = 1LL << 60;
struct Link {
int dest, sig;
long long cap;
} aristas[MAXM * 2];
int cnt = 1, cab[MAXN];
long long flujoMaximo;
void agregarArista(int origen, int destino, long long capacidad) {
aristas[++cnt] = {destino, cab[origen], capacidad};
cab[origen] = cnt;
aristas[++cnt] = {origen, cab[destino], 0};
cab[destino] = cnt;
}
int nodos, arcos, fuente, sumidero;
long long nivel[MAXN];
int padre[MAXN];
bool marcado[MAXN];
bool bfs() {
memset(marcado, 0, sizeof(marcado));
std::queue<int> cola;
cola.push(fuente);
marcado[fuente] = true;
nivel[fuente] = INF_CAP;
while (!cola.empty()) {
int u = cola.front();
cola.pop();
for (int idx = cab[u]; idx; idx = aristas[idx].sig) {
if (aristas[idx].cap == 0) continue;
int v = aristas[idx].dest;
if (marcado[v]) continue;
nivel[v] = std::min(nivel[u], aristas[idx].cap);
padre[v] = idx;
cola.push(v);
marcado[v] = true;
if (v == sumidero) return true;
}
}
return false;
}
void aplicarFlujo() {
int vertice = sumidero;
while (vertice != fuente) {
int arco = padre[vertice];
aristas[arco].cap -= nivel[sumidero];
aristas[arco ^ 1].cap += nivel[sumidero];
vertice = aristas[arco ^ 1].dest;
}
flujoMaximo += nivel[sumidero];
}
int main() {
scanf("%d%d%d%d", &nodos, &arcos, &fuente, &sumidero);
for (int i = 0; i < arcos; i++) {
int u, v;
long long w;
scanf("%d%d%lld", &u, &v, &w);
agregarArista(u, v, w);
}
while (bfs()) aplicarFlujo();
printf("%lld\n", flujoMaximo);
return 0;
}
Dinic
Complejidad: \\(\\mathcal{O}(n^2 m)\\). Funciona bien para grafos densos con \\(n \\leq 10^4\\) a \\(10^5\\). Para emparejamiento máximo en grafos bipartitos alcanza \\(\\mathcal{O}(m\\sqrt{n})\\).
La idea es construir un grafo por capas usando BFS, donde \\(d[x]\\) representa la distancia mínima en aristas desde la fuente hasta \\(x\\). Luego se ejecuta DFS sobre este grafo, buscando múltiples caminos aumentantes y actualizando las capacidades al retroceder.
Optimización de arco actual: para un nodo \\(u\\), cuando se recorre la lista de aristas hasta la posición \\(i\\), las primeras \\(i-1\\) ya están saturadas. Se guarda un puntero \\(nw[u]\\) que indica desde dónde continuar en la siguiente visita.
// Flujo máximo con Dinic
const int MAXN = 210, MAXM = 5010;
const long long INF_CAP = 1LL << 60;
struct Link {
int dest, sig;
long long cap;
} aristas[MAXM * 2];
int cnt = 1, cab[MAXN], ptr[MAXN];
long long dist[MAXN];
int nodos, arcos, fuente, sumidero;
long long flujoMaximo;
void agregarArista(int ori, int dst, long long cap) {
aristas[++cnt] = {dst, cab[ori], cap};
cab[ori] = cnt;
aristas[++cnt] = {ori, cab[dst], 0};
cab[dst] = cnt;
}
bool bfs() {
for (int i = 1; i <= nodos; i++) dist[i] = INF_CAP;
std::queue<int> cola;
cola.push(fuente);
dist[fuente] = 0;
ptr[fuente] = cab[fuente];
while (!cola.empty()) {
int u = cola.front();
cola.pop();
for (int idx = cab[u]; idx; idx = aristas[idx].sig) {
int v = aristas[idx].dest;
if (aristas[idx].cap > 0 && dist[v] == INF_CAP) {
cola.push(v);
ptr[v] = cab[v];
dist[v] = dist[u] + 1;
if (v == sumidero) return true;
}
}
}
return false;
}
long long dfs(int u, long long entrada) {
if (u == sumidero) return entrada;
long long acumulado = 0;
for (int &i = ptr[u]; i && entrada; i = aristas[i].sig) {
int v = aristas[i].dest;
if (aristas[i].cap > 0 && dist[v] == dist[u] + 1) {
long long empujado = dfs(v, std::min(entrada, aristas[i].cap));
if (empujado == 0) dist[v] = INF_CAP;
aristas[i].cap -= empujado;
aristas[i ^ 1].cap += empujado;
acumulado += empujado;
entrada -= empujado;
}
}
return acumulado;
}
int main() {
scanf("%d%d%d%d", &nodos, &arcos, &fuente, &sumidero);
for (int i = 0; i < arcos; i++) {
int u, v;
long long w;
scanf("%d%d%lld", &u, &v, &w);
agregarArista(u, v, w);
}
while (bfs()) flujoMaximo += dfs(fuente, INF_CAP);
printf("%lld\n", flujoMaximo);
return 0;
}
ISAP
Complejidad: \\(\\mathcal{O}(n^2 m)\\). A diferencia de Dinic, solo ejecuta BFS una vez para inicializar los niveles. Durante la búsqueda DFS, los niveles se van incrementando.
Se mantiene un arreglo \\(gap[i]\\) que cuenta cuántos nodos tienen nivel \\(i\\). Cuando \\(gap[i] = 0\\) para algún \\(i\\), se produce una desconexión en el grafo de capas y se puede detener la búsqueda. Cada nodo actualiza su nivel al valor mínimo de sus vecinos más uno.
// Flujo máximo con ISAP
const int MAXN = 210, MAXM = 5010;
const long long INF_CAP = 1LL << 60;
struct Link {
int dest, sig;
long long cap;
} aristas[MAXM * 2];
int cnt = 1, cab[MAXN], puntero[MAXN];
int nivel[MAXN], brecha[MAXN];
int nodos, arcos, fuente, sumidero;
long long flujoMaximo;
void agregarArista(int ori, int dst, long long cap) {
aristas[++cnt] = {dst, cab[ori], cap};
cab[ori] = cnt;
aristas[++cnt] = {ori, cab[dst], 0};
cab[dst] = cnt;
}
void construirNiveles() {
memset(nivel, -1, sizeof(nivel));
memset(brecha, 0, sizeof(brecha));
nivel[sumidero] = 0;
brecha[0] = 1;
std::queue<int> cola;
cola.push(sumidero);
while (!cola.empty()) {
int u = cola.front();
cola.pop();
for (int idx = cab[u]; idx; idx = aristas[idx].sig) {
int v = aristas[idx].dest;
if (nivel[v] != -1) continue;
cola.push(v);
nivel[v] = nivel[u] + 1;
brecha[nivel[v]]++;
}
}
}
long long buscarFlujo(int u, long long disponible) {
if (u == sumidero) {
flujoMaximo += disponible;
return disponible;
}
long long resultado = 0;
for (int &i = puntero[u]; i; i = aristas[i].sig) {
int v = aristas[i].dest;
if (aristas[i].cap && nivel[v] + 1 == nivel[u]) {
long long parcial = buscarFlujo(v, std::min(aristas[i].cap, disponible));
if (parcial) {
aristas[i].cap -= parcial;
aristas[i ^ 1].cap += parcial;
disponible -= parcial;
resultado += parcial;
}
if (disponible == 0) return resultado;
}
}
brecha[nivel[u]]--;
if (brecha[nivel[u]] == 0) nivel[fuente] = nodos + 1;
nivel[u]++;
brecha[nivel[u]]++;
return resultado;
}
int main() {
scanf("%d%d%d%d", &nodos, &arcos, &fuente, &sumidero);
for (int i = 0; i < arcos; i++) {
int u, v;
long long w;
scanf("%d%d%lld", &u, &v, &w);
agregarArista(u, v, w);
}
construirNiveles();
flujoMaximo = 0;
while (nivel[fuente] < nodos) {
memcpy(puntero, cab, sizeof(cab));
buscarFlujo(fuente, INF_CAP);
}
printf("%lld\n", flujoMaximo);
return 0;
}
HLPP (Preflujo con etiquetas de mayor nivel)
Complejidad: \\(\\mathcal{O}(n^2 \\sqrt{m})\\). A diferencia de los métodos anteriores basados en caminos aumentantes, este algoritmo pertenece a la familia de preflujos.
Idea central: se permite que el flujo se acumule temporalmente en nodos intermedios (llamados exceso). Cada nodo tiene una altura, y solo se permite enviar flujo hacia nodos de altura menor. Si un nodo no puede enviar su exceso, se reeleva incrementando su altura.
El algoritmo utiliza una cola de prioridad ordenada por altura. Procesa nodos desde el de mayor altura, intentando empujar flujo hacia vecinos con altura exactamante uno menor. Si no puede empujar, reeleva el nodo.
// Preflujo con etiquetas de mayor nivel (HLPP)
const int MAXN = 1203;
const int INF_VAL = 0x3f3f3f3f;
struct Arco {
int destino, reverso, capacidad;
Arco(int d, int r, int c) : destino(d), reverso(r), capacidad(c) {}
};
std::vector<Arco> red[MAXN];
int alt[MAXN], contAlt[MAXN];
int exceso[MAXN];
int operaciones, alturaMax;
std::vector<int> capa[MAXN], conExceso[MAXN];
void insertarArista(int ori, int dst, int cap) {
red[ori].emplace_back(dst, (int)red[dst].size(), cap);
red[dst].emplace_back(ori, (int)red[ori].size() - 1, 0);
}
void actualizarAltura(int nodo, int nuevaAlt) {
++operaciones;
if (alt[nodo] != INF_VAL) --contAlt[alt[nodo]];
alt[nodo] = nuevaAlt;
if (nuevaAlt == INF_VAL) return;
++contAlt[nuevaAlt];
alturaMax = nuevaAlt;
capa[nuevaAlt].push_back(nodo);
if (exceso[nodo] > 0) conExceso[nuevaAlt].push_back(nodo);
}
void reetiquetar() {
operaciones = 0;
memset(alt, 0x3f, sizeof(alt));
memset(contAlt, 0, sizeof(contAlt));
for (int i = 0; i <= alturaMax + 1; i++) {
capa[i].clear();
conExceso[i].clear();
}
alt[sumidero] = 0;
std::queue<int> cola;
cola.push(sumidero);
while (!cola.empty()) {
int u = cola.front();
cola.pop();
for (auto &arco : red[u]) {
if (alt[arco.destino] == INF_VAL && red[arco.destino][arco.reverso].capacidad > 0) {
cola.push(arco.destino);
actualizarAltura(arco.destino, alt[u] + 1);
}
}
alturaMax = alt[u];
}
}
void empujar(int u, Arco &arco) {
if (exceso[arco.destino] == 0)
conExceso[alt[arco.destino]].push_back(arco.destino);
int cant = std::min(exceso[u], arco.capacidad);
arco.capacidad -= cant;
red[arco.destino][arco.reverso].capacidad += cant;
exceso[u] -= cant;
exceso[arco.destino] += cant;
}
void procesarNodo(int u) {
int nuevaAlt = INF_VAL;
for (auto &arco : red[u]) {
if (arco.capacidad > 0) {
if (alt[u] == alt[arco.destino] + 1) {
empujar(u, arco);
if (exceso[u] <= 0) return;
} else {
nuevaAlt = std::min(nuevaAlt, alt[arco.destino] + 1);
}
}
}
if (contAlt[alt[u]] > 1) {
actualizarAltura(u, nuevaAlt);
} else {
for (int h = alt[u]; h < MAXN; h++) {
for (int nodo : capa[h])
actualizarAltura(nodo, INF_VAL);
capa[h].clear();
}
}
}
int flujoHLPP() {
memset(exceso, 0, sizeof(exceso));
exceso[fuente] = INF_VAL;
reetiquetar();
for (auto &arco : red[fuente])
empujar(fuente, arco);
for (int h = alturaMax; h >= 0; h--) {
while (!conExceso[h].empty()) {
int nodo = conExceso[h].back();
conExceso[h].pop_back();
procesarNodo(nodo);
if (operaciones > 20000) reetiquetar();
}
}
return exceso[sumidero];
}
int nodos, arcos, fuente, sumidero;
int main() {
scanf("%d%d%d%d", &nodos, &arcos, &fuente, &sumidero);
for (int i = 0; i < arcos; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
insertarArista(u, v, w);
}
printf("%d\n", flujoHLPP());
return 0;
}
Corte mínimo
Conceptos fundamentales
Dado un grafo de flujo \\(G=(V,E)\\), una partición \\((S, T)\\) de los nodos donde la fuente \\(s \\in S\\) y el sumidero \\(t \\in T\\), la capacidad del corte es la suma de las capacidades de todas las aristas de \\(S\\) hacia \\(T\\).
Teorema de flujo máximo y corte mínimo: el flujo máximo es igual a la capacidad del corte mínimo, es decir, \\(f(s,t)_{\\max} = c(S,T)_{\\min}\\).
Para recuperar los nodos del conjunto \\(S\\), se ejecuta DFS desde la fuente recorriendo solo aristas con capacidad residual positiva. Para contar el número de aristas del corte, basta asignar capacidad unitaria a cada arista y ejecutar Dinic.
Modelo de corte mínimo aplicado
Dados dos conjuntos \\(A\\) y \\(B\\), y \\(n\\) elementos donde el elemento \\(i\\) tiene costo \\(a_i\\) en \\(A\\) y \\(b_i\\) en \\(B\\), con restricciones adicionales \\((u_i, v_i, w_i\\) indicando costo \\(w_i\\) si \\(u_i\\) y \\(v_i\\) están en conjuntos distintos), se modela como un corte mínimo de selección binaria.
Se construye un grafo con fuente \\(s\\) y sumidero \\(t\\): desde \\(s\\) hacia el nodo \\(i\\) se coloca una arista de capacidad \\(a_i\\), y desde \\(i\\) hacia \\(t\\) una de capacidad \\(b_i\\). Entre \\(u_i\\) y \\(v_i\\) se colocan aristas bidireccionales de capacidad \\(w_i\\). El corte mínimo corresponde al costo mínimo.
Flujo de costo mínimo
Cada arista tiene además un costo unitario \\(w(u,v)\\). Si por la arista \\((u,v)\\) circula un flujo \\(f(u,v)\\), el costo asociado es \\(f(u,v) \\times w(u,v)\\).
SSP (Camino más corto sucesivo)
Basado en el algoritmo EK, se sustituye la búsqueda BFS por una búsqueda de camino de menor costo usando SPFA. Es equivalente a buscar el camino más corto en la red residual usando el costo como peso.
// Flujo de costo mínimo con SSP
const int MAXN = 410, MAXM = 15010;
const int INF = 0x3f3f3f3f;
struct ArcoFlujo {
int destino, siguiente, flujo, costo;
ArcoFlujo(int d = 0, int s = 0, int f = 0, int c = 0)
: destino(d), siguiente(s), flujo(f), costo(c) {}
} red[MAXM * 2];
int totalArcos = 1, cabeza[MAXN];
int ant[MAXN], distancia[MAXN];
int flujoTotal, costoTotal;
bool enCola[MAXN];
int numNodos, numArcos, origen, destino;
void agregarArco(int u, int v, int flujo, int costo) {
red[++totalArcos] = ArcoFlujo(v, cabeza[u], flujo, costo);
cabeza[u] = totalArcos;
red[++totalArcos] = ArcoFlujo(u, cabeza[v], 0, -costo);
cabeza[v] = totalArcos;
}
bool spfa() {
for (int i = 1; i <= numNodos; i++) {
enCola[i] = false;
distancia[i] = INF;
}
std::queue<int> cola;
cola.push(origen);
distancia[origen] = 0;
while (!cola.empty()) {
int u = cola.front();
cola.pop();
enCola[u] = false;
for (int idx = cabeza[u]; idx; idx = red[idx].siguiente) {
int v = red[idx].destino;
if (red[idx].flujo > 0 && distancia[v] > distancia[u] + red[idx].costo) {
distancia[v] = distancia[u] + red[idx].costo;
ant[v] = idx;
if (!enCola[v]) {
enCola[v] = true;
cola.push(v);
}
}
}
}
return distancia[destino] != INF;
}
void enviarFlujo() {
int minimo = INF;
for (int v = destino; v != origen; v = red[ant[v] ^ 1].destino)
minimo = std::min(minimo, red[ant[v]].flujo);
for (int v = destino; v != origen; v = red[ant[v] ^ 1].destino) {
red[ant[v]].flujo -= minimo;
red[ant[v] ^ 1].flujo += minimo;
costoTotal += minimo * red[ant[v]].costo;
}
flujoTotal += minimo;
}
int main() {
scanf("%d%d%d%d", &numNodos, &numArcos, &origen, &destino);
for (int i = 0; i < numArcos; i++) {
int u, v, f, c;
scanf("%d%d%d%d", &u, &v, &f, &c);
agregarArco(u, v, f, c);
}
while (spfa()) enviarFlujo();
printf("%d %d\n", flujoTotal, costoTotal);
return 0;
}
Variante basada en Dinic
Se adapta Dinic sustituyendo BFS por SPFA para encontrar el camino de menor costo. La BFS origianl genera el grafo por capas, pero aquí se reemplaza por una búsqueda de camino más corto ponderado por costos.
Para la optimización con Dijkstra (algoritmo Primal-Dual), se requiere calcular potenciales para eliminar arcos con peso negativo.
// Flujo de costo mínimo estilo Dinic
const int MAXN = 410, MAXM = 15010;
const int INF = 0x3f3f3f3f;
struct ArcoFlujo {
int destino, siguiente, flujo, costo;
ArcoFlujo(int d = 0, int s = 0, int f = 0, int c = 0)
: destino(d), siguiente(s), flujo(f), costo(c) {}
} red[MAXM * 2];
int totalArcos = 1, cabeza[MAXN];
int dist[MAXN], puntero[MAXN];
int flujoTotal, costoTotal;
bool visitado[MAXN];
int numNodos, numArcos, origen, destino;
void agregarArco(int u, int v, int flujo, int costo) {
red[++totalArcos] = ArcoFlujo(v, cabeza[u], flujo, costo);
cabeza[u] = totalArcos;
red[++totalArcos] = ArcoFlujo(u, cabeza[v], 0, -costo);
cabeza[v] = totalArcos;
}
bool bfs() {
for (int i = 1; i <= numNodos; i++) {
dist[i] = INF;
visitado[i] = false;
}
std::queue<int> cola;
cola.push(origen);
dist[origen] = 0;
puntero[origen] = cabeza[origen];
visitado[origen] = true;
while (!cola.empty()) {
int u = cola.front();
cola.pop();
visitado[u] = false;
for (int idx = cabeza[u]; idx; idx = red[idx].siguiente) {
int v = red[idx].destino;
if (red[idx].flujo > 0 && dist[v] > dist[u] + red[idx].costo) {
puntero[v] = cabeza[v];
dist[v] = dist[u] + red[idx].costo;
if (!visitado[v]) {
visitado[v] = true;
cola.push(v);
}
}
}
}
return dist[destino] != INF;
}
long long dfs(int u, long long entrada) {
if (u == destino) return entrada;
visitado[u] = true;
long long acumulado = 0;
for (int &i = puntero[u]; i && entrada; i = red[i].siguiente) {
int v = red[i].destino;
if (!visitado[v] && red[i].flujo > 0 && dist[v] == dist[u] + red[i].costo) {
long long empujado = dfs(v, std::min((long long)red[i].flujo, entrada));
if (empujado) {
red[i].flujo -= empujado;
red[i ^ 1].flujo += empujado;
acumulado += empujado;
entrada -= empujado;
costoTotal += red[i].costo * empujado;
}
}
}
visitado[u] = false;
return acumulado;
}
int main() {
scanf("%d%d%d%d", &numNodos, &numArcos, &origen, &destino);
for (int i = 0; i < numArcos; i++) {
int u, v, f, c;
scanf("%d%d%d%d", &u, &v, &f, &c);
agregarArco(u, v, f, c);
}
while (bfs()) flujoTotal += dfs(origen, INF);
printf("%d %d\n", flujoTotal, costoTotal);
return 0;
}
Flujos con cotas inferiores y superiores
Resuelve problemas donde cada arista tiene una capacidad mínima \\(low\\) y máxima \\(up\\).
Flujo factible sin fuente ni sumidero distinguidos
Problema: dado un grafo con \\(n\\) nodos y \\(m\\) aristas, cada una con cotas \\(low\\) y \\(up\\), encontrar un flujo que satisfaga conservación en todos los nodos.
Método: se separa la cota inferior del flujo. Para cada arista se construye una arista con capacidad \\(up - low\\), y se registra el desbalance \\(c[i]\\) en cada nodo causado por los flujos obligatorios \\(low\\). Luego se añaden nodos virtuales (superfuente \\(S'\\) y supersumidero \\(T'\\)): desde \\(S'\\) hacia nodos con \\(c[i] > 0\\) con capacidad \\(c[i]\\), y desde nodos con \\(c[i] < 0\\) hacia \\(T'\\) con capacidad \\(-c[i]\\). Si el flujo máximo desde \\(S'\\) hasta \\(T'\\) iguala \\(\\sum_{c[i]>0} c[i]\\), existe solución factible.
// Flujo factible con cotas (sin fuente/sumidero explícitos)
int main() {
int n, m;
scanf("%d%d", &n, &m);
int src = n + 1, snk = n + 2;
int desbalance[MAXN] = {};
int cotasBajas[MAXM];
for (int i = 0; i < m; i++) {
int u, v, lb, ub;
scanf("%d%d%d%d", &u, &v, &lb, &ub);
agregarArco(u, v, ub - lb);
desbalance[v] += lb;
desbalance[u] -= lb;
cotasBajas[i] = lb;
}
int sumaRequerida = 0;
for (int i = 1; i <= n; i++) {
if (desbalance[i] > 0) {
agregarArco(src, i, desbalance[i]);
sumaRequerida += desbalance[i];
}
if (desbalance[i] < 0)
agregarArco(i, snk, -desbalance[i]);
}
origen = src;
destino = snk;
while (bfs()) flujoTotal += dfs(origen, INF);
if (flujoTotal == sumaRequerida) {
printf("YES\n");
for (int i = 3, j = 0; j < m; i += 2, j++)
printf("%d\n", red[i].flujo + cotasBajas[j]);
} else {
printf("NO\n");
}
return 0;
}
Flujo factible con fuente y sumidero
La fuente y sumidero originales no conservan flujo. Se añade una arista artificial desde \\(T\\) hacia \\(S\\) con cota inferior 0 y superior infinito, y se resuelve como el caso anterior. El flujo factible corresponde al flujo en la arista inversa de \\(T \\to S\\).
Flujo máximo con cotas
Después de hallar un flujo factible (usando nodos virtuales), se ejecuta un flujo máximo adicional en la red residual entre la fuente y sumidero reales. El resultado total es la suma del flujo factible y el flujo adicional.
Flujo mínimo con cotas
Se halla primero el flujo factible. Luego se busca reducir el flujo al máximo posible eliminando ciclos de \\(T\\) a \\(S\\). Se ejecuta un flujo máximo desde \\(T\\) hasta \\(S\\) (sin la arista artificial) y se resta al flujo factible.