Semana 11 — Flujo máximo
Objetivos
- Explicar por qué la red residual permite deshacer decisiones.
- Demostrar el teorema de flujo máximo y corte mínimo.
- Implementar Ford-Fulkerson y Edmonds-Karp, y explicar su costo.
Sesión A — Flujo máximo: Ford-Fulkerson
Lectura: Apuntes, semana 11.
Apoyo: Erickson, secs. 10.1 (Flows), 10.2 (Cuts) y 10.4 (Ford and Fulkerson’s augmenting-path algorithm). CLRS, capítulo Maximum Flow, 4.ª edición.
Temas:
- El problema: cuánto pasa de la fuente al sumidero respetando las capacidades y la conservación.
- Un greedy que falla: empujar por cualquier camino y no volver atrás, con un contraejemplo.
- La red residual: las aristas hacia atrás permiten deshacer.
- Ford-Fulkerson: mientras haya un camino de aumento, empujar.
- Con capacidades enteras, termina con flujo entero, en O(E·f). Con capacidades grandes, ese costo puede ser muy malo, con un ejemplo.
- Representación en C++: aristas en pares, donde
e ^ 1es la arista inversa. - Error común: olvidar crear la arista inversa con capacidad 0.
Sesión B — Teorema de flujo máximo y corte mínimo · Edmonds-Karp
Lectura: Apuntes, semana 11.
Apoyo: Erickson, secs. 10.3 (The Maxflow-Mincut Theorem) y 10.6 (Edmonds and Karp’s Algorithms). CLRS, capítulo Maximum Flow, 4.ª edición.
Temas:
- Cortes: la capacidad de cualquier corte acota cualquier flujo.
- El teorema: el flujo máximo es igual al corte mínimo. Demostración con lo alcanzable en la red residual.
- Encontrar el corte mínimo al terminar el algoritmo.
- Edmonds-Karp: siempre el camino de aumento con menos aristas, usando BFS. Costo O(VE²), sin depender de las capacidades. Se da la idea de la demostración.
- En la práctica: otros algoritmos, como Dinic y los de preflujo, son muy usados.
- Error común: decir que el corte mínimo son las aristas saturadas: no toda arista saturada cruza el corte.
Laboratorio — Práctica 3 · Opcional: capacidad de una red
Práctica 3 en la sesión de laboratorio.
Problema opcional: dada una red de oleoductos o de enlaces con capacidades, calcular cuánto puede enviarse entre dos puntos, y qué tramos forman el cuello de botella.
Entregas
- Práctica 3: Programación dinámica. Ver
practicas/README.md.
Preguntas de repaso
- Corran Ford-Fulkerson a mano en una red de 4 nodos en la que un mal camino obligue a usar una arista inversa.
- Demuestren que el valor de un flujo nunca supera la capacidad de un corte.
- Con Ford-Fulkerson y capacidades de 1000000, ¿cuántas iteraciones puede hacer en el peor caso? Den la red.
- Dado un flujo máximo, ¿cómo se encuentra un corte mínimo?
- Si se aumenta en 1 la capacidad de una arista del corte mínimo, ¿siempre aumenta el flujo máximo? ¿Por qué?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (7)Pruebas (1)Laboratorio (4)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// El diamante con capacidades grandes: cuántas iteraciones hace Ford-Fulkerson con cada regla.
// Va con -O2 porque la regla adversaria hace millones de iteraciones.
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>
#include "flow_checks.h"
namespace {
template <typename Rule>
void run_rule(const char* name, long long big, Rule rule) {
FlowNetwork net = build_network(4, diamond_network(big));
const auto start = std::chrono::steady_clock::now();
const FlowRun run = ford_fulkerson(net, 0, 3, rule);
const std::chrono::duration<double, std::milli> elapsed = std::chrono::steady_clock::now() - start;
std::cout << std::setw(10) << big << std::setw(26) << name << std::setw(12) << run.value << std::setw(12)
<< run.iterations << std::setw(12) << std::fixed << std::setprecision(1) << elapsed.count() << '\n';
}
} // namespace
int main() {
std::cout << "capacidad regla flujo iteraciones ms\n";
for (long long big : {10LL, 1000LL, 100000LL, 1000000LL}) {
run_rule("el más largo", big, longest_path_rule);
run_rule("primero de un DFS", big, depth_first_rule);
run_rule("BFS (Edmonds-Karp)", big, shortest_path_rule);
}
}// Cortes: cada corte acota el flujo, el flujo neto por cualquier corte es el mismo, y el corte
// mínimo se lee en la red original. También: una arista saturada no siempre cruza, y aumentar una
// arista del corte no siempre aumenta el flujo.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include "flow_checks.h"
namespace {
using Names = std::vector<std::string>;
std::string side_name(unsigned mask, const Names& names) {
std::string text = "{";
for (std::size_t v = 0; v < names.size(); v++) {
if (on_source_side(mask, static_cast<int>(v))) text += (text.size() > 1 ? ", " : "") + names[v];
}
return text + "}";
}
std::string edge_name(const FlowNetwork& net, int edge, const Names& names) {
return names[static_cast<std::size_t>(net.tail(edge))] + " -> " + names[static_cast<std::size_t>(net.head(edge))];
}
// Las aristas originales (números pares) que van del lado de la fuente al otro lado.
void print_crossing(const FlowNetwork& net, const std::vector<char>& side, const Names& names) {
long long total = 0;
std::cout << " aristas del corte:";
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
if (side[static_cast<std::size_t>(net.tail(edge))] && !side[static_cast<std::size_t>(net.head(edge))]) {
std::cout << " " << edge_name(net, edge, names) << " (" << net.capacity(edge) << ")";
total += net.capacity(edge);
}
}
std::cout << "\n capacidad: " << total << '\n';
}
void print_saturated(const FlowNetwork& net, const std::vector<char>& side, const Names& names) {
long long total = 0;
std::cout << " aristas saturadas:\n";
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
if (net.flow_on(edge) != net.capacity(edge)) continue;
const bool crosses = side[static_cast<std::size_t>(net.tail(edge))] && !side[static_cast<std::size_t>(net.head(edge))];
std::cout << " " << edge_name(net, edge, names) << " (" << net.capacity(edge) << ")"
<< (crosses ? " cruza\n" : " no cruza\n");
total += net.capacity(edge);
}
std::cout << " suma de las saturadas: " << total << '\n';
}
void print_all_cuts(const FlowNetwork& net, const Names& names) {
std::cout << " lado de s capacidad flujo neto\n";
for (unsigned mask : all_cuts(net.node_count(), 0, net.node_count() - 1)) {
std::cout << " " << std::left << std::setw(14) << side_name(mask, names) << std::right << std::setw(8)
<< cut_capacity(net, mask) << std::setw(13) << net_across_cut(net, mask) << '\n';
}
}
long long flow_of(int nodes, const std::vector<EdgeSpec>& edges) {
FlowNetwork net = build_network(nodes, edges);
return edmonds_karp(net, 0, nodes - 1).value;
}
void first_network_part() {
const Names names = {"s", "a", "b", "t"};
FlowNetwork net = build_network(4, first_network());
const FlowRun run = ford_fulkerson(net, 0, 3, longest_path_rule);
std::cout << "La primera red, con su flujo máximo de valor " << run.value << ":\n";
print_all_cuts(net, names);
const std::vector<char> side = residual_side(net, 0);
std::cout << " alcanzable en la red residual: " << side_name(mask_of(side), names) << '\n';
print_crossing(net, side, names);
}
void saturated_part() {
const Names names = {"s", "a", "b", "t"};
std::cout << "\nUna arista saturada que no cruza (s -> a 2, s -> b 2, a -> b 1, a -> t 1, b -> t 2):\n";
FlowNetwork net = build_network(4, saturated_network());
const FlowRun run = edmonds_karp(net, 0, 3);
std::cout << " flujo máximo: " << run.value << ", cortes mínimos: " << count_min_cuts(net, 0, 3) << '\n';
print_all_cuts(net, names);
const std::vector<char> side = residual_side(net, 0);
std::cout << " con BFS, alcanzable en la red residual: " << side_name(mask_of(side), names) << '\n';
print_crossing(net, side, names);
print_saturated(net, side, names);
FlowNetwork other = build_network(4, saturated_network());
ford_fulkerson(other, 0, 3, longest_path_rule);
const std::vector<char> other_side = residual_side(other, 0);
std::cout << " con otro flujo máximo del mismo valor (el camino más largo primero), alcanzable: "
<< side_name(mask_of(other_side), names) << '\n';
print_crossing(other, other_side, names);
print_saturated(other, other_side, names);
}
void increase_part() {
const Names names = {"s", "a", "t"};
std::cout << "\nDos cortes mínimos en serie (s -> a 5, a -> t 5):\n";
FlowNetwork net = build_network(3, {{0, 1, 5}, {1, 2, 5}});
std::cout << " flujo máximo: " << edmonds_karp(net, 0, 2).value << ", cortes mínimos: " << count_min_cuts(net, 0, 2)
<< '\n';
print_all_cuts(net, names);
std::cout << " con s -> a de 6: flujo " << flow_of(3, {{0, 1, 6}, {1, 2, 5}}) << '\n';
std::cout << " con a -> t de 6: flujo " << flow_of(3, {{0, 1, 5}, {1, 2, 6}}) << '\n';
std::cout << " con las dos de 6: flujo " << flow_of(3, {{0, 1, 6}, {1, 2, 6}}) << '\n';
std::cout << "\nCon un único corte mínimo (la red de la arista saturada), al aumentar en 1:\n";
const std::vector<EdgeSpec> base = saturated_network();
const Names four = {"s", "a", "b", "t"};
const FlowNetwork labels = build_network(4, base);
for (std::size_t k = 0; k < base.size(); k++) {
std::vector<EdgeSpec> edges = base;
edges[k].capacity++;
std::cout << " " << edge_name(labels, 2 * static_cast<int>(k), four) << ": flujo " << flow_of(4, edges) << '\n';
}
}
} // namespace
int main() {
first_network_part();
saturated_part();
increase_part();
}// Edmonds-Karp, paso a paso: el camino de cada vuelta, su largo, las aristas críticas y las
// distancias en la red residual, que nunca bajan.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include "flow_checks.h"
namespace {
const std::vector<std::string> NAMES = {"s", "a", "b", "c", "d", "t"};
std::string arc_text(const FlowNetwork& net, int arc) {
return NAMES[static_cast<std::size_t>(net.tail(arc))] + (arc % 2 == 0 ? "->" : "~>") +
NAMES[static_cast<std::size_t>(net.head(arc))];
}
void print_distances(const std::vector<int>& dist) {
std::cout << " distancias:";
for (std::size_t v = 0; v < dist.size(); v++) {
std::cout << ' ' << NAMES[v] << '=';
if (dist[v] < 0) std::cout << '-';
else std::cout << dist[v];
}
std::cout << '\n';
}
} // namespace
int main() {
FlowNetwork net = build_network(6, trace_network());
int round = 0;
print_distances(residual_distances(net, 0));
while (true) {
const std::vector<int> path = shortest_path_rule(net, 0, 5);
if (path.empty()) break;
const long long amount = net.bottleneck(path);
round++;
std::cout << "vuelta " << round << ": " << path_name(net, path, NAMES, 0) << " " << path.size()
<< " aristas, empuja " << amount << '\n';
std::cout << " críticas:";
for (int arc : path) {
if (net.residual(arc) == amount) std::cout << ' ' << arc_text(net, arc);
}
std::cout << '\n';
net.push(path, amount);
print_distances(residual_distances(net, 0));
}
std::cout << "flujo máximo: " << net.flow_value(0) << ", corte mínimo por fuerza bruta: " << brute_min_cut(net, 0, 5)
<< '\n';
std::cout << "\nLas mismas iteraciones si todas las capacidades se multiplican:\n";
for (long long factor : {1LL, 1000LL, 1000000LL}) {
std::vector<EdgeSpec> edges = trace_network();
for (EdgeSpec& e : edges) e.capacity *= factor;
FlowNetwork scaled = build_network(6, edges);
const FlowRun run = edmonds_karp(scaled, 0, 5);
std::cout << " por " << std::setw(7) << factor << ": flujo " << std::setw(9) << run.value << ", iteraciones "
<< run.iterations << '\n';
}
}// Árbitros de las pruebas: comprobar un flujo con la definición, recorrer todos los cortes, probar
// todos los caminos, y las redes de ejemplo de los apuntes. Nada de esto es rápido.
#pragma once
#include <cstddef>
#include <limits>
#include <random>
#include <string>
#include <vector>
#include "flow.h"
struct EdgeSpec {
int from;
int to;
long long capacity;
};
inline FlowNetwork build_network(int nodes, const std::vector<EdgeSpec>& edges) {
FlowNetwork net(nodes);
for (const EdgeSpec& e : edges) net.add_edge(e.from, e.to, e.capacity);
return net;
}
// Capacidades y conservación, con la definición. El nodo source y el nodo sink no conservan.
inline bool flow_is_valid(const FlowNetwork& net, int source, int sink) {
std::vector<long long> net_out(static_cast<std::size_t>(net.node_count()), 0);
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
const long long f = net.flow_on(edge);
if (f < 0 || f > net.capacity(edge)) return false;
net_out[static_cast<std::size_t>(net.tail(edge))] += f;
net_out[static_cast<std::size_t>(net.head(edge))] -= f;
}
for (int v = 0; v < net.node_count(); v++) {
if (v != source && v != sink && net_out[static_cast<std::size_t>(v)] != 0) return false;
}
return true;
}
// Un corte se describe con una máscara: el bit v dice si el nodo v está del lado de la fuente.
inline bool on_source_side(unsigned mask, int v) { return (mask >> v) & 1U; }
// Capacidad de un corte: solo cuentan las aristas que van del lado de la fuente al otro.
inline long long cut_capacity(const FlowNetwork& net, unsigned mask) {
long long total = 0;
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
if (on_source_side(mask, net.tail(edge)) && !on_source_side(mask, net.head(edge))) {
total += net.capacity(edge);
}
}
return total;
}
// Flujo neto a través de un corte: lo que cruza hacia allá menos lo que vuelve.
inline long long net_across_cut(const FlowNetwork& net, unsigned mask) {
long long total = 0;
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
const bool tail_in = on_source_side(mask, net.tail(edge));
const bool head_in = on_source_side(mask, net.head(edge));
if (tail_in && !head_in) total += net.flow_on(edge);
if (!tail_in && head_in) total -= net.flow_on(edge);
}
return total;
}
// Todas las máscaras con source de un lado y sink del otro.
inline std::vector<unsigned> all_cuts(int nodes, int source, int sink) {
std::vector<unsigned> cuts;
for (unsigned mask = 0; mask < (1U << nodes); mask++) {
if (on_source_side(mask, source) && !on_source_side(mask, sink)) cuts.push_back(mask);
}
return cuts;
}
inline long long brute_min_cut(const FlowNetwork& net, int source, int sink) {
long long best = std::numeric_limits<long long>::max();
for (unsigned mask : all_cuts(net.node_count(), source, sink)) best = std::min(best, cut_capacity(net, mask));
return best;
}
inline int count_min_cuts(const FlowNetwork& net, int source, int sink) {
const long long best = brute_min_cut(net, source, sink);
int count = 0;
for (unsigned mask : all_cuts(net.node_count(), source, sink)) count += cut_capacity(net, mask) == best;
return count;
}
inline unsigned mask_of(const std::vector<char>& side) {
unsigned mask = 0;
for (std::size_t v = 0; v < side.size(); v++) {
if (side[v]) mask |= 1U << v;
}
return mask;
}
// Prueba todos los caminos simples con capacidad residual desde u. Se usa por la regla del camino más largo
// y por el greedy sin arista inversa.
inline void all_simple_paths(const FlowNetwork& net, int u, int sink, bool forward_only, std::vector<char>& seen,
std::vector<int>& path, std::vector<std::vector<int>>& found) {
if (u == sink) {
found.push_back(path);
return;
}
seen[static_cast<std::size_t>(u)] = 1;
for (int arc : net.arcs_from(u)) {
if (forward_only && arc % 2 != 0) continue;
const int v = net.head(arc);
if (net.residual(arc) > 0 && !seen[static_cast<std::size_t>(v)]) {
path.push_back(arc);
all_simple_paths(net, v, sink, forward_only, seen, path, found);
path.pop_back();
}
}
seen[static_cast<std::size_t>(u)] = 0;
}
inline std::vector<std::vector<int>> simple_paths(const FlowNetwork& net, int source, int sink, bool forward_only) {
std::vector<char> seen(static_cast<std::size_t>(net.node_count()), 0);
std::vector<int> path;
std::vector<std::vector<int>> found;
all_simple_paths(net, source, sink, forward_only, seen, path, found);
return found;
}
// Una regla adversaria: el camino de aumento con más aristas. Con empate, el primero que aparece.
inline std::vector<int> longest_path_rule(const FlowNetwork& net, int source, int sink) {
std::vector<int> best;
for (const std::vector<int>& path : simple_paths(net, source, sink, false)) {
if (path.size() > best.size()) best = path;
}
return best;
}
// El greedy que no vuelve atrás: la misma regla, sin usar nunca una arista inversa.
inline std::vector<int> longest_forward_rule(const FlowNetwork& net, int source, int sink) {
std::vector<int> best;
for (const std::vector<int>& path : simple_paths(net, source, sink, true)) {
if (path.size() > best.size()) best = path;
}
return best;
}
// Todos los valores finales posibles del greedy que no vuelve atrás, según qué camino elija en cada paso.
inline void greedy_outcomes(FlowNetwork net, int source, int sink, std::vector<long long>& outcomes) {
const std::vector<std::vector<int>> paths = simple_paths(net, source, sink, true);
if (paths.empty()) {
outcomes.push_back(net.flow_value(source));
return;
}
for (const std::vector<int>& path : paths) {
FlowNetwork next = net;
next.push(path, next.bottleneck(path));
greedy_outcomes(next, source, sink, outcomes);
}
}
// La red con s, a, b, t = 0, 1, 2, 3 de la que se habla en todo el capítulo.
inline std::vector<EdgeSpec> first_network() {
return {{0, 1, 3}, {0, 2, 2}, {1, 2, 2}, {1, 3, 2}, {2, 3, 3}};
}
// La red con una arista saturada que no cruza el único corte mínimo.
inline std::vector<EdgeSpec> saturated_network() {
return {{0, 1, 2}, {0, 2, 2}, {1, 2, 1}, {1, 3, 1}, {2, 3, 2}};
}
// La red del recorrido de Edmonds-Karp, con s, a, b, c, d, t = 0, 1, 2, 3, 4, 5.
inline std::vector<EdgeSpec> trace_network() {
return {{0, 2, 4}, {0, 3, 6}, {1, 5, 3}, {2, 1, 6}, {2, 4, 5}, {3, 1, 2}, {3, 2, 2}, {4, 5, 5}};
}
// El diamante: cuatro aristas de capacidad big y una arista de capacidad 1 en medio.
inline std::vector<EdgeSpec> diamond_network(long long big) {
return {{0, 1, big}, {0, 2, big}, {1, 2, 1}, {1, 3, big}, {2, 3, big}};
}
// Red al azar en la que el nodo 0 es la fuente y el nodo nodes - 1 es el sumidero. Puede tener
// aristas paralelas, antiparalelas, que entren a la fuente y que salgan del sumidero.
inline std::vector<EdgeSpec> random_edges(std::mt19937& rng, int nodes, int edges, unsigned max_capacity) {
std::vector<EdgeSpec> result;
for (int k = 0; k < edges; k++) {
const int from = static_cast<int>(rng() % static_cast<unsigned>(nodes));
int to = static_cast<int>(rng() % static_cast<unsigned>(nodes));
if (to == from) to = (to + 1) % nodes;
result.push_back({from, to, 1 + static_cast<long long>(rng() % max_capacity)});
}
return result;
}
// Un camino, para imprimir: > sigue una arista y < recorre una inversa, contra la arista.
inline std::string path_name(const FlowNetwork& net, const std::vector<int>& path,
const std::vector<std::string>& names, int source) {
std::string text = names[static_cast<std::size_t>(source)];
for (int arc : path) {
text += arc % 2 == 0 ? " > " : " < ";
text += names[static_cast<std::size_t>(net.head(arc))];
}
return text;
}// Flujo máximo. Las aristas se guardan en pares: la arista original tiene un número par e y su
// inversa es e ^ 1. Lo único que se guarda de cada una es su capacidad residual.
#pragma once
#include <algorithm>
#include <cstddef>
#include <limits>
#include <queue>
#include <vector>
class FlowNetwork {
public:
explicit FlowNetwork(int nodes) : arcs_from_(static_cast<std::size_t>(nodes)) {}
// Agrega from → to y, junto con ella, su inversa con capacidad 0. Devuelve el número de la
// arista, que siempre es par. Dos aristas antiparalelas son dos pares independientes.
int add_edge(int from, int to, long long capacity) {
const int edge = static_cast<int>(to_.size());
to_.push_back(to);
residual_.push_back(capacity);
arcs_from_[static_cast<std::size_t>(from)].push_back(edge);
to_.push_back(from);
residual_.push_back(0);
arcs_from_[static_cast<std::size_t>(to)].push_back(edge + 1);
return edge;
}
int node_count() const { return static_cast<int>(arcs_from_.size()); }
int edge_count() const { return static_cast<int>(to_.size()) / 2; }
int head(int arc) const { return to_[static_cast<std::size_t>(arc)]; }
int tail(int arc) const { return to_[static_cast<std::size_t>(arc ^ 1)]; }
long long residual(int arc) const { return residual_[static_cast<std::size_t>(arc)]; }
const std::vector<int>& arcs_from(int node) const { return arcs_from_[static_cast<std::size_t>(node)]; }
// De una arista original: lo que pasa por ella es lo que su inversa puede devolver.
long long flow_on(int edge) const { return residual(edge ^ 1); }
long long capacity(int edge) const { return residual(edge) + residual(edge ^ 1); }
// Valor del flujo: lo que sale de source menos lo que entra.
long long flow_value(int source) const {
long long net = 0;
for (int arc : arcs_from(source)) {
if (arc % 2 == 0) net += flow_on(arc);
else net -= flow_on(arc ^ 1);
}
return net;
}
// Empuja amount por cada arco del camino. Empujar por un arco es quitarle a él y darle a su par.
void push(const std::vector<int>& path, long long amount) {
for (int arc : path) {
residual_[static_cast<std::size_t>(arc)] -= amount;
residual_[static_cast<std::size_t>(arc ^ 1)] += amount;
}
}
long long bottleneck(const std::vector<int>& path) const {
long long smallest = std::numeric_limits<long long>::max();
for (int arc : path) smallest = std::min(smallest, residual(arc));
return smallest;
}
private:
std::vector<int> to_;
std::vector<long long> residual_;
std::vector<std::vector<int>> arcs_from_;
};
// Distancias en aristas desde source en la red residual. -1 si el nodo no se alcanza.
inline std::vector<int> residual_distances(const FlowNetwork& net, int source) {
std::vector<int> dist(static_cast<std::size_t>(net.node_count()), -1);
std::queue<int> pending;
dist[static_cast<std::size_t>(source)] = 0;
pending.push(source);
while (!pending.empty()) {
const int u = pending.front();
pending.pop();
for (int arc : net.arcs_from(u)) {
const int v = net.head(arc);
if (net.residual(arc) > 0 && dist[static_cast<std::size_t>(v)] < 0) {
dist[static_cast<std::size_t>(v)] = dist[static_cast<std::size_t>(u)] + 1;
pending.push(v);
}
}
}
return dist;
}
// Regla de Edmonds-Karp: el camino de aumento con menos aristas, con BFS. Vacío si no hay.
inline std::vector<int> shortest_path_rule(const FlowNetwork& net, int source, int sink) {
std::vector<int> arc_into(static_cast<std::size_t>(net.node_count()), -1);
std::queue<int> pending;
pending.push(source);
while (!pending.empty() && arc_into[static_cast<std::size_t>(sink)] < 0) {
const int u = pending.front();
pending.pop();
for (int arc : net.arcs_from(u)) {
const int v = net.head(arc);
if (v != source && net.residual(arc) > 0 && arc_into[static_cast<std::size_t>(v)] < 0) {
arc_into[static_cast<std::size_t>(v)] = arc;
pending.push(v);
}
}
}
std::vector<int> path;
if (arc_into[static_cast<std::size_t>(sink)] < 0) return path;
for (int v = sink; v != source; v = net.tail(arc_into[static_cast<std::size_t>(v)])) {
path.push_back(arc_into[static_cast<std::size_t>(v)]);
}
std::reverse(path.begin(), path.end());
return path;
}
// Regla de DFS: el primer camino que encuentra una búsqueda en profundidad. Vacío si no hay.
inline std::vector<int> depth_first_rule(const FlowNetwork& net, int source, int sink) {
std::vector<char> seen(static_cast<std::size_t>(net.node_count()), 0);
std::vector<int> path;
// Pila explícita: por cada nodo del camino, cuántos de sus arcos ya se probaron.
std::vector<std::size_t> next_arc = {0};
int u = source;
seen[static_cast<std::size_t>(source)] = 1;
while (u != sink) {
const std::vector<int>& arcs = net.arcs_from(u);
if (next_arc.back() == arcs.size()) {
next_arc.pop_back();
if (path.empty()) return {};
u = net.tail(path.back());
path.pop_back();
continue;
}
const int arc = arcs[next_arc.back()++];
const int v = net.head(arc);
if (net.residual(arc) > 0 && !seen[static_cast<std::size_t>(v)]) {
seen[static_cast<std::size_t>(v)] = 1;
path.push_back(arc);
next_arc.push_back(0);
u = v;
}
}
return path;
}
struct Augmentation {
std::vector<int> path;
long long amount;
};
struct FlowRun {
long long value;
long long iterations;
};
// Ford-Fulkerson: mientras la regla encuentre un camino de aumento, empujar su cuello de botella.
// Si log no es nulo, guarda cada aumento.
template <typename Rule>
FlowRun ford_fulkerson(FlowNetwork& net, int source, int sink, Rule rule, std::vector<Augmentation>* log = nullptr) {
long long iterations = 0;
while (true) {
const std::vector<int> path = rule(net, source, sink);
if (path.empty()) break;
const long long amount = net.bottleneck(path);
net.push(path, amount);
iterations++;
if (log != nullptr) log->push_back({path, amount});
}
return {net.flow_value(source), iterations};
}
// Edmonds-Karp es Ford-Fulkerson con la regla del camino más corto.
inline FlowRun edmonds_karp(FlowNetwork& net, int source, int sink, std::vector<Augmentation>* log = nullptr) {
return ford_fulkerson(net, source, sink, shortest_path_rule, log);
}
// Al terminar el algoritmo, estos nodos son el lado de la fuente de un corte mínimo.
inline std::vector<char> residual_side(const FlowNetwork& net, int source) {
const std::vector<int> dist = residual_distances(net, source);
std::vector<char> side(dist.size(), 0);
for (std::size_t v = 0; v < dist.size(); v++) side[v] = dist[v] >= 0;
return side;
}// El greedy que no vuelve atrás se atasca. Ford-Fulkerson, con la misma regla y con aristas
// inversas, llega al máximo.
#include <cstddef>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include "flow_checks.h"
namespace {
const std::vector<std::string> NAMES = {"s", "a", "b", "t"};
void print_log(const FlowNetwork& net, const std::vector<Augmentation>& log) {
long long total = 0;
for (const Augmentation& step : log) {
total += step.amount;
std::cout << " " << path_name(net, step.path, NAMES, 0) << " empuja " << step.amount << ", total " << total
<< '\n';
}
}
void print_edges(const FlowNetwork& net) {
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
std::cout << " " << NAMES[static_cast<std::size_t>(net.tail(edge))] << " -> "
<< NAMES[static_cast<std::size_t>(net.head(edge))] << " flujo " << net.flow_on(edge) << " de "
<< net.capacity(edge) << '\n';
}
}
} // namespace
int main() {
const std::vector<EdgeSpec> edges = first_network();
std::cout << "Sin volver atrás, siempre el camino con más aristas:\n";
FlowNetwork stuck = build_network(4, edges);
std::vector<Augmentation> stuck_log;
const FlowRun greedy = ford_fulkerson(stuck, 0, 3, longest_forward_rule, &stuck_log);
print_log(stuck, stuck_log);
std::cout << " no queda camino: se queda en " << greedy.value << '\n';
print_edges(stuck);
std::cout << "\nSin volver atrás, todas las formas de elegir los caminos:\n";
std::vector<long long> outcomes;
greedy_outcomes(build_network(4, edges), 0, 3, outcomes);
std::map<long long, int> tally;
for (long long value : outcomes) tally[value]++;
for (const auto& [value, times] : tally) {
std::cout << " termina en " << value << ": " << times << " de " << outcomes.size() << " secuencias\n";
}
std::cout << "\nFord-Fulkerson, la misma regla con aristas inversas (< es recorrer una inversa):\n";
FlowNetwork net = build_network(4, edges);
std::vector<Augmentation> log;
const FlowRun run = ford_fulkerson(net, 0, 3, longest_path_rule, &log);
print_log(net, log);
std::cout << " no queda camino: termina en " << run.value << '\n';
print_edges(net);
std::cout << "\nCorte mínimo por fuerza bruta: " << brute_min_cut(net, 0, 3) << '\n';
// Dar capacidad a la inversa desde el inicio es permitir la arista en los dos sentidos.
std::cout << "\nSi la inversa se crea con capacidad c en lugar de 0, en s -> b, a -> b, a -> t, todas de 1:\n";
const std::vector<EdgeSpec> blocked = {{0, 2, 1}, {1, 2, 1}, {1, 3, 1}};
FlowNetwork right = build_network(4, blocked);
std::cout << " con capacidad 0: flujo " << edmonds_karp(right, 0, 3).value << '\n';
FlowNetwork wrong = build_network(4, {{0, 2, 1}, {2, 0, 1}, {1, 2, 1}, {2, 1, 1}, {1, 3, 1}, {3, 1, 1}});
std::cout << " con capacidad c: flujo " << edmonds_karp(wrong, 0, 3).value << '\n';
}// Edmonds-Karp frente a la cota O(VE) de iteraciones y a la regla de DFS, en redes por capas con
// capacidades al azar. Mide con -O2, una sola corrida por fila: los tiempos dependen de la máquina.
#include <chrono>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
#include "flow_checks.h"
namespace {
// Capas de width nodos entre la fuente y el sumidero, cada nodo con aristas a la capa siguiente.
// Con shuffled, las aristas se agregan en orden al azar, y los arcos de cada nodo quedan en otro orden.
FlowNetwork layered(int layers, int width, int out_degree, unsigned max_capacity, unsigned seed, bool shuffled = false) {
std::mt19937 rng(seed);
const int nodes = layers * width + 2;
const int sink = nodes - 1;
std::vector<EdgeSpec> edges;
const auto node = [width](int layer, int k) { return 1 + layer * width + k; };
const auto capacity = [&rng, max_capacity] { return 1 + static_cast<long long>(rng() % max_capacity); };
for (int k = 0; k < width; k++) {
edges.push_back({0, node(0, k), capacity()});
edges.push_back({node(layers - 1, k), sink, capacity()});
}
for (int layer = 0; layer + 1 < layers; layer++) {
for (int k = 0; k < width; k++) {
for (int d = 0; d < out_degree; d++) {
edges.push_back({node(layer, k), node(layer + 1, static_cast<int>(rng() % static_cast<unsigned>(width))), capacity()});
}
}
}
if (shuffled) {
for (std::size_t i = edges.size(); i > 1; i--) std::swap(edges[i - 1], edges[rng() % i]);
}
return build_network(nodes, edges);
}
template <typename Rule>
void measure(const char* name, FlowNetwork net, Rule rule) {
const int sink = net.node_count() - 1;
const auto start = std::chrono::steady_clock::now();
const FlowRun run = ford_fulkerson(net, 0, sink, rule);
const std::chrono::duration<double, std::milli> elapsed = std::chrono::steady_clock::now() - start;
std::cout << std::setw(7) << net.node_count() << std::setw(8) << net.edge_count() << std::setw(8) << name
<< std::setw(16) << run.value << std::setw(12) << run.iterations << std::setw(12)
<< static_cast<long long>(net.node_count()) * net.edge_count() << std::setw(11) << std::fixed
<< std::setprecision(1) << elapsed.count() << '\n';
}
} // namespace
int main() {
std::cout << " V E regla flujo iteraciones VE ms\n";
for (int layers : {10, 20, 40}) {
const FlowNetwork net = layered(layers, 10, 3, 1000000000U, 7U);
measure("BFS", net, shortest_path_rule);
measure("DFS", net, depth_first_rule);
}
std::cout << "\nLa red de 402 nodos, con las aristas agregadas en orden al azar:\n";
std::cout << " V E regla flujo iteraciones VE ms\n";
measure("BFS", layered(40, 10, 3, 1000000000U, 7U, true), shortest_path_rule);
measure("DFS", layered(40, 10, 3, 1000000000U, 7U, true), depth_first_rule);
std::cout << "\nLa misma red de 402 nodos con otras capacidades máximas, solo BFS:\n";
std::cout << " V E regla flujo iteraciones VE ms\n";
for (unsigned max_capacity : {10U, 1000U, 1000000U, 1000000000U}) {
measure("BFS", layered(40, 10, 3, max_capacity, 7U), shortest_path_rule);
}
}Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
// Comprueba lo que afirman los apuntes. Se compila con sanitizers.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <map>
#include <random>
#include <vector>
#include "flow.h"
#include "flow_checks.h"
namespace {
void test_pairs() {
FlowNetwork net(3);
const int first = net.add_edge(0, 1, 7);
const int second = net.add_edge(1, 0, 4); // antiparalela: otro par, independiente
assert(first == 0 && second == 2);
assert((first ^ 1) == 1 && (second ^ 1) == 3);
assert(net.head(first) == 1 && net.tail(first) == 0);
assert(net.head(first ^ 1) == 0 && net.tail(first ^ 1) == 1);
assert(net.residual(first) == 7 && net.residual(first ^ 1) == 0);
assert(net.capacity(second) == 4 && net.flow_on(second) == 0);
net.push({first}, 3);
assert(net.flow_on(first) == 3 && net.residual(first) == 4 && net.residual(first ^ 1) == 3);
assert(net.flow_on(second) == 0 && net.capacity(first) == 7);
}
void test_first_network() {
const std::vector<EdgeSpec> edges = first_network();
FlowNetwork stuck = build_network(4, edges);
assert(ford_fulkerson(stuck, 0, 3, longest_forward_rule).value == 4);
assert(flow_is_valid(stuck, 0, 3));
std::vector<long long> outcomes;
greedy_outcomes(build_network(4, edges), 0, 3, outcomes);
std::map<long long, int> tally;
for (long long value : outcomes) tally[value]++;
assert(tally.size() == 2 && tally[4] == 2 && tally[5] == 4);
FlowNetwork net = build_network(4, edges);
std::vector<Augmentation> log;
const FlowRun run = ford_fulkerson(net, 0, 3, longest_path_rule, &log);
assert(run.value == 5 && run.iterations == 3);
assert(brute_min_cut(net, 0, 3) == 5);
assert(log[1].path.size() == 3 && log[1].path[1] % 2 == 1); // la segunda vuelta usa una inversa
assert(count_min_cuts(net, 0, 3) == 2);
// El error común: la inversa con capacidad c deja pasar flujo por una arista al revés.
FlowNetwork right = build_network(4, {{0, 2, 1}, {1, 2, 1}, {1, 3, 1}});
assert(edmonds_karp(right, 0, 3).value == 0);
FlowNetwork wrong = build_network(4, {{0, 2, 1}, {2, 0, 1}, {1, 2, 1}, {2, 1, 1}, {1, 3, 1}, {3, 1, 1}});
assert(edmonds_karp(wrong, 0, 3).value == 1);
}
void test_diamond() {
for (long long big : {1LL, 10LL, 1000LL, 1000000LL}) {
FlowNetwork adversary = build_network(4, diamond_network(big));
const FlowRun bad = ford_fulkerson(adversary, 0, 3, longest_path_rule);
assert(bad.value == 2 * big && bad.iterations == 2 * big); // la pregunta de repaso 3
FlowNetwork shortest = build_network(4, diamond_network(big));
const FlowRun good = edmonds_karp(shortest, 0, 3);
assert(good.value == 2 * big && good.iterations == 2);
}
FlowNetwork dfs = build_network(4, diamond_network(1000000));
const FlowRun run = ford_fulkerson(dfs, 0, 3, depth_first_rule);
assert(run.value == 2000000 && run.iterations == 4);
// El total no cabe en int, aunque cada capacidad sí.
FlowNetwork large = build_network(4, diamond_network(2000000000));
assert(edmonds_karp(large, 0, 3).value == 4000000000LL);
}
// La definición: en todo corte, flujo neto = valor ≤ capacidad. Y el corte que da lo alcanzable.
void check_flow_and_cuts(const FlowNetwork& net, int source, int sink, long long value) {
assert(flow_is_valid(net, source, sink));
assert(net.flow_value(source) == value);
for (unsigned mask : all_cuts(net.node_count(), source, sink)) {
assert(net_across_cut(net, mask) == value);
assert(value <= cut_capacity(net, mask));
}
const std::vector<char> side = residual_side(net, source);
assert(side[static_cast<std::size_t>(source)] && !side[static_cast<std::size_t>(sink)]);
assert(cut_capacity(net, mask_of(side)) == value);
for (int e = 0; e < net.edge_count(); e++) {
const int edge = 2 * e;
const bool tail_in = side[static_cast<std::size_t>(net.tail(edge))];
const bool head_in = side[static_cast<std::size_t>(net.head(edge))];
if (tail_in && !head_in) assert(net.flow_on(edge) == net.capacity(edge));
if (!tail_in && head_in) assert(net.flow_on(edge) == 0);
}
}
void test_random_networks() {
std::mt19937 rng(11);
for (int round = 0; round < 3000; round++) {
const int nodes = 2 + static_cast<int>(rng() % 6);
const int count = static_cast<int>(rng() % 14);
const unsigned max_capacity = round % 2 == 0 ? 5U : 1000000000U;
const std::vector<EdgeSpec> edges = random_edges(rng, nodes, count, max_capacity);
const int sink = nodes - 1;
FlowNetwork by_bfs = build_network(nodes, edges);
const long long expected = brute_min_cut(by_bfs, 0, sink);
const FlowRun bfs = edmonds_karp(by_bfs, 0, sink);
assert(bfs.value == expected);
check_flow_and_cuts(by_bfs, 0, sink, expected);
FlowNetwork by_dfs = build_network(nodes, edges);
assert(ford_fulkerson(by_dfs, 0, sink, depth_first_rule).value == expected);
check_flow_and_cuts(by_dfs, 0, sink, expected);
// Cuesta millones de vueltas con capacidades grandes: esta regla solo con las pequeñas.
if (max_capacity == 5U) {
FlowNetwork by_long = build_network(nodes, edges);
assert(ford_fulkerson(by_long, 0, sink, longest_path_rule).value == expected);
check_flow_and_cuts(by_long, 0, sink, expected);
}
}
}
void test_edges_around_source_and_sink() {
// Un ciclo por la fuente no aporta al valor. Una arista que sale del sumidero tampoco.
FlowNetwork net = build_network(3, {{0, 1, 5}, {1, 0, 5}, {1, 2, 1}, {2, 1, 4}});
assert(edmonds_karp(net, 0, 2).value == 1);
assert(brute_min_cut(net, 0, 2) == 1);
// Fuente y sumidero sin conexión: flujo 0, corte sin aristas.
FlowNetwork apart = build_network(4, {{0, 1, 3}, {2, 3, 3}});
assert(edmonds_karp(apart, 0, 3).value == 0);
assert(cut_capacity(apart, mask_of(residual_side(apart, 0))) == 0);
// Solo una arista hacia atrás: tampoco hay flujo.
FlowNetwork back = build_network(2, {{1, 0, 9}});
assert(edmonds_karp(back, 0, 1).value == 0);
assert(brute_min_cut(back, 0, 1) == 0);
}
long long flow_of(int nodes, const std::vector<EdgeSpec>& edges) {
FlowNetwork net = build_network(nodes, edges);
return edmonds_karp(net, 0, nodes - 1).value;
}
void test_saturated_outside_the_cut() {
FlowNetwork net = build_network(4, saturated_network());
assert(edmonds_karp(net, 0, 3).value == 3);
assert(count_min_cuts(net, 0, 3) == 1); // un solo corte mínimo: no hay otro donde pueda cruzar
const std::vector<char> side = residual_side(net, 0);
assert(side[0] && side[1] && side[2] && !side[3]);
const int s_to_b = 2;
assert(net.flow_on(s_to_b) == net.capacity(s_to_b));
long long saturated = 0;
for (int e = 0; e < net.edge_count(); e++) {
if (net.flow_on(2 * e) == net.capacity(2 * e)) saturated += net.capacity(2 * e);
}
assert(saturated == 5);
}
void test_increase_one_edge() {
assert(flow_of(3, {{0, 1, 5}, {1, 2, 5}}) == 5);
assert(flow_of(3, {{0, 1, 6}, {1, 2, 5}}) == 5);
assert(flow_of(3, {{0, 1, 5}, {1, 2, 6}}) == 5);
assert(flow_of(3, {{0, 1, 6}, {1, 2, 6}}) == 6);
assert(count_min_cuts(build_network(3, {{0, 1, 5}, {1, 2, 5}}), 0, 2) == 2);
std::mt19937 rng(23);
int unique_cases = 0;
for (int round = 0; round < 2000; round++) {
const int nodes = 2 + static_cast<int>(rng() % 5);
std::vector<EdgeSpec> edges = random_edges(rng, nodes, 1 + static_cast<int>(rng() % 10), 6U);
FlowNetwork net = build_network(nodes, edges);
const long long before = edmonds_karp(net, 0, nodes - 1).value;
const bool unique = count_min_cuts(net, 0, nodes - 1) == 1;
const std::vector<char> side = residual_side(net, 0);
for (std::size_t k = 0; k < edges.size(); k++) {
std::vector<EdgeSpec> raised = edges;
raised[k].capacity++;
const long long after = flow_of(nodes, raised);
assert(after == before || after == before + 1); // nunca sube más de 1
const bool crosses = side[static_cast<std::size_t>(edges[k].from)] && !side[static_cast<std::size_t>(edges[k].to)];
if (unique && crosses) {
assert(after == before + 1); // con corte único, una arista suya sí sube el flujo
unique_cases++;
}
}
}
assert(unique_cases > 100);
}
void test_edmonds_karp_idea() {
// Las distancias residuales no bajan, cada arco es crítico a lo sumo V / 2 veces, y hay a lo sumo VE vueltas.
std::mt19937 rng(37);
for (int round = 0; round < 3000; round++) {
const int nodes = 2 + static_cast<int>(rng() % 9);
const int count = static_cast<int>(rng() % 26);
FlowNetwork net = build_network(nodes, random_edges(rng, nodes, count, 20U));
const int sink = nodes - 1;
std::vector<int> critical(2 * static_cast<std::size_t>(count), 0);
std::vector<int> dist = residual_distances(net, 0);
long long rounds = 0;
while (true) {
const std::vector<int> path = shortest_path_rule(net, 0, sink);
if (path.empty()) break;
assert(static_cast<int>(path.size()) == dist[static_cast<std::size_t>(sink)]);
const long long amount = net.bottleneck(path);
for (int arc : path) {
if (net.residual(arc) == amount) critical[static_cast<std::size_t>(arc)]++;
}
net.push(path, amount);
rounds++;
const std::vector<int> next = residual_distances(net, 0);
for (std::size_t v = 0; v < next.size(); v++) {
if (dist[v] < 0) assert(next[v] < 0); // lo inalcanzable sigue inalcanzable
else if (next[v] >= 0) assert(next[v] >= dist[v]); // la distancia no baja
}
dist = next;
}
for (int times : critical) assert(times <= nodes / 2);
assert(rounds <= static_cast<long long>(nodes) * count);
}
}
void test_trace_network() {
FlowNetwork net = build_network(6, trace_network());
std::vector<Augmentation> log;
const FlowRun run = edmonds_karp(net, 0, 5, &log);
assert(run.value == 8 && run.iterations == 4 && brute_min_cut(net, 0, 5) == 8);
assert(log[0].path.size() == 3 && log[1].path.size() == 3 && log[2].path.size() == 4 && log[3].path.size() == 5);
// El corte de los apuntes: S = {s, c}, y sus aristas s -> b, c -> a, c -> b suman 8.
const std::vector<char> side = residual_side(net, 0);
assert(mask_of(side) == ((1U << 0) | (1U << 3)));
assert(cut_capacity(net, mask_of(side)) == 8);
assert(net.flow_on(2 * 7) == net.capacity(2 * 7)); // d -> t saturada, con los dos extremos en T
assert(net.flow_on(2 * 3) == 1); // b -> a bajó de 3 a 1 en la última vuelta
for (long long factor : {1000LL, 1000000LL, 1000000000LL}) {
std::vector<EdgeSpec> edges = trace_network();
for (EdgeSpec& e : edges) e.capacity *= factor;
FlowNetwork scaled = build_network(6, edges);
const FlowRun same = edmonds_karp(scaled, 0, 5);
assert(same.value == 8 * factor && same.iterations == 4);
}
}
} // namespace
int main() {
test_pairs();
test_first_network();
test_diamond();
test_random_networks();
test_edges_around_source_and_sink();
test_saturated_outside_the_cut();
test_increase_one_edge();
test_edmonds_karp_idea();
test_trace_network();
std::cout << "Todas las pruebas de la semana 11 pasaron.\n";
}Laboratorio
Archivos de partida del laboratorio de la semana.
TIEMPO = 1
VERIFICADOR = verificador.cpp
include ../../../lab.mk# La capacidad de una red
Una empresa transporta combustible por una red de oleoductos. La red tiene n estaciones y m tramos. Cada tramo va de una
estación a otra, **en un solo sentido**, y tiene una capacidad: los barriles por minuto que puede llevar como máximo.
La empresa quiere enviar combustible de la estación s a la estación t, de forma continua. En las demás estaciones no se
guarda nada ni se produce nada: por minuto, lo que entra es igual a lo que sale. Por un tramo puede pasar cualquier
cantidad entre 0 y su capacidad. Se cuenta como enviado lo que sale de s menos lo que vuelve a entrar en s.
Ustedes responden dos cosas:
1. La mayor cantidad de barriles por minuto que se puede enviar de s a t.
2. Qué tramos son el cuello de botella: una lista de tramos tal que, si se cierran todos, ya no hay manera de ir de s a
t siguiendo los tramos en su sentido, y cuyas capacidades suman **exactamente** la cantidad de la respuesta 1.
Siempre existe una lista así, y como toda capacidad es al menos 1, no le sobra ningún tramo.
## Entrada
La primera línea tiene cuatro enteros: n, m, s y t. Las estaciones se numeran de 1 a n. Luego vienen m líneas, una por
tramo, cada una con tres enteros `u v c`: el tramo va de u a v y tiene capacidad c. Los tramos se numeran de 1 a m, en el
orden en que aparecen.
Puede haber varios tramos entre las mismas dos estaciones, en el mismo sentido o en sentidos contrarios. También puede
haber tramos que entran a s o que salen de t.
## Salida
- Una línea con la cantidad máxima.
- Una línea con k, la cantidad de tramos de la lista.
- Una línea con los k números de esos tramos, en cualquier orden. Si k = 0, esa línea queda vacía o no se escribe.
Puede haber varias listas correctas, y cualquiera vale: un verificador revisa su respuesta.
## Límites
- 2 ≤ n ≤ 500
- 0 ≤ m ≤ 5000
- 1 ≤ s, t ≤ n, con s ≠ t
- 1 ≤ u, v ≤ n, con u ≠ v
- 1 ≤ c ≤ 10⁹
## Ejemplo
Entrada:
```text
5 7 1 5
1 2 6
1 3 4
2 3 3
2 4 2
3 4 2
3 5 4
4 5 5
```
Salida:
```text
8
3
4 5 6
```
Se pueden enviar 8 barriles por minuto. Los tramos 4, 5 y 6 tienen capacidades 2, 2 y 4, que suman 8. Si se cierran, de
las estaciones 1, 2 y 3 ya no se puede pasar a las estaciones 4 y 5.
## Tiempo
1 segundo por caso, compilado con `-O2`. Corran `make test` para probar con el juez.// La capacidad de una red: lee la red y responde que hay que cerrar todos los tramos. Cerrarlos
// deja a t sin nada, pero casi nunca es la respuesta correcta. Reemplacen el cálculo.
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
int n = 0;
int m = 0;
int s = 0;
int t = 0;
std::cin >> n >> m >> s >> t;
std::vector<int> from(static_cast<std::size_t>(m));
std::vector<int> to(static_cast<std::size_t>(m));
std::vector<long long> capacity(static_cast<std::size_t>(m));
for (std::size_t k = 0; k < from.size(); k++) std::cin >> from[k] >> to[k] >> capacity[k];
// Por hacer: calcular cuánto se puede enviar y qué tramos lo limitan.
long long total = 0;
for (long long c : capacity) total += c;
std::cout << total << '\n' << m << '\n';
for (int k = 1; k <= m; k++) std::cout << k << (k == m ? "" : " ");
std::cout << '\n';
}// Verificador de "La capacidad de una red": verificador ENTRADA ESPERADA SALIDA.
// En ESPERADA está solo la cantidad máxima. Se comprueba que salga esa cantidad, que los tramos
// sean válidos y distintos, que su capacidad sume esa cantidad y que, sin ellos, s ya no llegue a t.
// Un conjunto así no tiene tramos de sobra: los que salen de lo que s todavía alcanza ya están en
// él y suman al menos la cantidad máxima, y toda capacidad es al menos 1.
// Termina con 0 si todo está bien, y con 1 y un mensaje si no.
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
namespace {
[[noreturn]] void reject(const std::string& reason) {
std::cout << reason << '\n';
std::exit(1);
}
// Convierte una palabra en número sin riesgo de overflow: solo dígitos, y a lo sumo 18.
bool parse_number(const std::string& word, long long& value) {
if (word.empty() || word.size() > 18) return false;
value = 0;
for (char c : word) {
if (c < '0' || c > '9') return false;
value = value * 10 + (c - '0');
}
return true;
}
} // namespace
int main(int argc, char* argv[]) {
if (argc != 4) reject("uso: verificador ENTRADA ESPERADA SALIDA");
std::ifstream input(argv[1]);
std::ifstream expected(argv[2]);
std::ifstream output(argv[3]);
std::size_t n = 0;
std::size_t m = 0;
std::size_t s = 0;
std::size_t t = 0;
input >> n >> m >> s >> t;
std::vector<std::size_t> from(m);
std::vector<std::size_t> to(m);
std::vector<long long> capacity(m);
for (std::size_t k = 0; k < m; k++) input >> from[k] >> to[k] >> capacity[k];
long long maximum = 0;
expected >> maximum;
std::string word;
long long amount = 0;
if (!(output >> word) || !parse_number(word, amount)) reject("la primera palabra no es un número válido");
if (amount != maximum) reject("cantidad máxima esperada: " + std::to_string(maximum) + ", salió " + word);
long long count = 0;
if (!(output >> word) || !parse_number(word, count)) reject("falta la cantidad de tramos");
if (count > static_cast<long long>(m)) reject("hay más tramos en la lista que en la red");
std::vector<char> closed(m, 0);
long long total = 0;
for (long long k = 0; k < count; k++) {
long long number = 0;
if (!(output >> word)) reject("faltan tramos en la lista");
if (!parse_number(word, number)) reject("número de tramo inválido: " + word);
if (number < 1 || number > static_cast<long long>(m)) reject("tramo fuera de rango: " + word);
const std::size_t edge = static_cast<std::size_t>(number - 1);
if (closed[edge]) reject("tramo repetido: " + word);
closed[edge] = 1;
total += capacity[edge];
}
if (output >> word) reject("sobra texto después de la lista: " + word);
if (total != maximum) {
reject("los tramos suman " + std::to_string(total) + " en lugar de " + std::to_string(maximum));
}
// Sin los tramos de la lista, t no se debe poder alcanzar desde s.
std::vector<std::vector<std::size_t>> out(n + 1);
for (std::size_t k = 0; k < m; k++) {
if (!closed[k]) out[from[k]].push_back(to[k]);
}
std::vector<char> seen(n + 1, 0);
std::queue<std::size_t> pending;
seen[s] = 1;
pending.push(s);
while (!pending.empty()) {
const std::size_t u = pending.front();
pending.pop();
for (std::size_t v : out[u]) {
if (!seen[v]) {
seen[v] = 1;
pending.push(v);
}
}
}
if (seen[t]) reject("sin esos tramos, s todavía llega a t");
return 0;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 11: flujo máximo. Ford-Fulkerson, red residual, cortes y Edmonds-Karp. Se usa dentro del
# entorno del curso.
#
# make compila los ejemplos en build/
# make test corre las pruebas de los ejemplos, con sanitizers
# make bench corre las mediciones, con -O2
# make clean borra lo generado
#
# El problema de lab/ tiene su propio Makefile y no entra aquí.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
BUILD = build
HEADERS = flow.h flow_checks.h
PROGRAMS = greedy_demo cut_demo ek_trace test_examples
BENCHES = bad_capacities iterations_bench
.PHONY: all test bench clean
all: $(PROGRAMS:%=$(BUILD)/%) $(BENCHES:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
# Lo que mide tiempos va con -O2 y sin sanitizers.
$(BENCHES:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
$(CXX) $(BENCHFLAGS) $< -o $@
$(BUILD):
mkdir -p $@
test: $(BUILD)/test_examples
$(BUILD)/test_examples
bench: $(BENCHES:%=$(BUILD)/%)
$(BUILD)/bad_capacities
$(BUILD)/iterations_bench
clean:
rm -rf $(BUILD)