// Eliminación en un campeonato de vóley sin empates. Los equipos son inventados.
#include <iostream>
#include <vector>

#include "baseball.h"

int main() {
    //                       0: Lima 1: Cusco 2: Ica 3: Piura 4: Callao
    Championship league{{"Lima", "Cusco", "Ica", "Piura", "Callao"},
                        {27, 26, 26, 25, 20},
                        {{0, 2, 2, 0, 0},
                         {2, 0, 2, 0, 0},
                         {2, 2, 0, 0, 0},
                         {0, 0, 0, 0, 3},
                         {0, 0, 0, 3, 0}}};
    std::cout << "equipo   ganados  faltan  máximo  ¿eliminado?\n";
    for (int x = 0; x < 5; x++) {
        Elimination result = check_team(league, x);
        std::cout << league.names[static_cast<std::size_t>(x)];
        for (std::size_t k = league.names[static_cast<std::size_t>(x)].size(); k < 9; k++) std::cout << ' ';
        std::cout << league.wins[static_cast<std::size_t>(x)] << "       " << remaining_of(league, x) << "       "
                  << result.best << "      ";
        if (!result.eliminated) {
            std::cout << "no (flujo " << result.flow << " de " << result.games_left << ")\n";
        } else if (result.trivial) {
            std::cout << "sí, a simple vista: "
                      << league.names[static_cast<std::size_t>(result.certificate[0])] << " ya lo pasó\n";
        } else {
            std::cout << "sí (flujo " << result.flow << " de " << result.games_left << ")\n";
        }
    }

    Elimination piura = check_team(league, 3);
    std::cout << "\nPiura: el grupo que lo elimina es";
    long long total = 0;
    for (int i : piura.certificate) {
        std::cout << ' ' << league.names[static_cast<std::size_t>(i)];
        total += league.wins[static_cast<std::size_t>(i)];
    }
    std::cout << "\n  victorias ya ganadas: " << total << '\n';
    long long inside = 0;
    for (std::size_t a = 0; a < piura.certificate.size(); a++) {
        for (std::size_t b = a + 1; b < piura.certificate.size(); b++) {
            inside += league.games[static_cast<std::size_t>(piura.certificate[a])]
                                  [static_cast<std::size_t>(piura.certificate[b])];
        }
    }
    std::cout << "  partidos entre ellos: " << inside << '\n';
    std::cout << "  máximo para que nadie pase a Piura: " << piura.certificate.size() << " x " << piura.best << " = "
              << static_cast<long long>(piura.certificate.size()) * piura.best << '\n';
    std::cout << "  fuerza bruta, ¿puede quedar primero?: " << (brute_can_finish_first(league, 3) ? "sí" : "no") << '\n';
}

// Eliminación en un campeonato sin empates: ¿puede un equipo todavía quedar primero, aunque sea empatado?
#pragma once

#include <cassert>
#include <cstddef>
#include <string>
#include <vector>

#include "flow.h"

struct Championship {
    std::vector<std::string> names;
    std::vector<int> wins;
    std::vector<std::vector<int>> games;  // games[i][j]: partidos que faltan entre i y j, simétrica
};

struct Elimination {
    bool eliminated = false;
    bool trivial = false;             // algún equipo ya tiene más victorias de las que x puede alcanzar
    long long best = 0;               // lo más que x puede alcanzar: W
    long long flow = 0;               // lo que pasó por la red
    long long games_left = 0;         // lo que debería pasar: los partidos que no juega x
    std::vector<int> certificate;     // equipos que, entre todos, no caben por debajo de W
};

inline int remaining_of(const Championship& league, int team) {
    int total = 0;
    for (int g : league.games[static_cast<std::size_t>(team)]) total += g;
    return total;
}

inline Elimination check_team(const Championship& league, int x) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    int teams = static_cast<int>(league.wins.size());
    Elimination result;
    result.best = league.wins[at(x)] + remaining_of(league, x);
    for (int i = 0; i < teams; i++) {
        if (league.wins[at(i)] > result.best) {
            // Sin este caso, la capacidad W - w sería negativa.
            result.eliminated = true;
            result.trivial = true;
            result.certificate = {i};
            return result;
        }
    }
    int game_nodes = 0;
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            if (i != x && j != x && league.games[at(i)][at(j)] > 0) game_nodes++;
        }
    }
    int source = teams;
    int sink = teams + 1;
    int next = teams + 2;
    MaxFlow flow(teams + 2 + game_nodes);
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            if (i != x && j != x) result.games_left += league.games[at(i)][at(j)];
        }
    }
    long long no_limit = result.games_left + 1;  // ningún partido reparte más que eso
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            if (i == x || j == x || league.games[at(i)][at(j)] == 0) continue;
            flow.add_edge(source, next, league.games[at(i)][at(j)]);
            flow.add_edge(next, i, no_limit);
            flow.add_edge(next, j, no_limit);
            next++;
        }
    }
    for (int i = 0; i < teams; i++) {
        if (i != x) flow.add_edge(i, sink, result.best - league.wins[at(i)]);
    }
    result.flow = flow.edmonds_karp(source, sink);
    result.eliminated = result.flow < result.games_left;
    if (result.eliminated) {
        std::vector<bool> reached = flow.reachable_from(source);
        for (int i = 0; i < teams; i++) {
            if (i != x && reached[at(i)]) result.certificate.push_back(i);
        }
    }
    return result;
}

// Lo que dice el certificado: las victorias de R, contando los partidos entre ellos, no caben debajo de W.
inline bool certificate_holds(const Championship& league, long long best, const std::vector<int>& group) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    long long total = 0;
    for (std::size_t a = 0; a < group.size(); a++) {
        total += league.wins[at(group[a])];
        for (std::size_t b = a + 1; b < group.size(); b++) total += league.games[at(group[a])][at(group[b])];
    }
    return total > static_cast<long long>(group.size()) * best;
}

// Árbitro: prueba todos los resultados de todos los partidos.
inline bool brute_can_finish_first(const Championship& league, int x) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    int teams = static_cast<int>(league.wins.size());
    std::vector<std::pair<int, int>> pending;
    for (int i = 0; i < teams; i++) {
        for (int j = i + 1; j < teams; j++) {
            for (int k = 0; k < league.games[at(i)][at(j)]; k++) pending.emplace_back(i, j);
        }
    }
    std::vector<int> final_wins = league.wins;
    auto search = [&](auto&& self, std::size_t next) -> bool {
        if (next == pending.size()) {
            for (int i = 0; i < teams; i++) {
                if (final_wins[at(i)] > final_wins[at(x)]) return false;
            }
            return true;
        }
        for (int winner : {pending[next].first, pending[next].second}) {
            final_wins[at(winner)]++;
            bool can = self(self, next + 1);
            final_wins[at(winner)]--;
            if (can) return true;
        }
        return false;
    };
    return search(search, 0);
}

// Caminos disjuntos: un flujo con un ciclo, aristas y nodos, no dirigido, y qué pasa si s y t son vecinos.
#include <iostream>
#include <string>
#include <vector>

#include "disjoint_paths.h"

namespace {

void print_trail(const std::vector<int>& trail, const std::string& names) {
    for (std::size_t k = 0; k < trail.size(); k++) {
        std::cout << (k ? " " : "") << names[static_cast<std::size_t>(trail[k])];
    }
}

void print_decomposition(const Decomposition& result, const std::string& names) {
    std::cout << "  caminos: " << result.paths.size() << '\n';
    for (const auto& path : result.paths) {
        std::cout << "    ";
        print_trail(path, names);
        std::cout << '\n';
    }
    for (const auto& cycle : result.cycles) {
        std::cout << "  ciclo apartado: ";
        print_trail(cycle, names);
        std::cout << '\n';
    }
}

}  // namespace

int main() {
    std::cout << "Un flujo de valor 2 con un ciclo, escrito a mano:\n";
    // s = 0, a = 1, b = 2, c = 3, d = 4, t = 5
    std::vector<Arc> with_cycle = {{0, 1}, {1, 2}, {2, 5}, {0, 3}, {3, 5}, {2, 4}, {4, 3}, {3, 2}};
    print_decomposition(decompose_flow(6, with_cycle, 0, 5), "sabcdt");

    // Un cuello de botella en c: s = 0, a = 1, b = 2, c = 3, d = 4, e = 5, t = 6
    const std::string names = "sabcdet";
    std::vector<Arc> arcs = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}, {4, 6}, {5, 6}};
    std::cout << "\nDirigido, sin compartir aristas:\n";
    print_decomposition(edge_disjoint_paths(7, arcs, 0, 6), names);
    std::cout << "  corte mínimo:";
    for (const Arc& arc : minimum_edge_cut(7, arcs, 0, 6)) {
        std::cout << ' ' << names[static_cast<std::size_t>(arc.from)] << "->" << names[static_cast<std::size_t>(arc.to)];
    }
    std::cout << "\n\nEl mismo grafo, sin compartir nodos:\n";
    print_decomposition(vertex_disjoint_paths(7, arcs, 0, 6), names);
    std::cout << "  separador mínimo:";
    for (int v : minimum_vertex_separator(7, arcs, 0, 6)) std::cout << ' ' << names[static_cast<std::size_t>(v)];
    std::cout << '\n';

    std::cout << "\nNo dirigido: el flujo de esta red usa una arista en las dos direcciones.\n";
    std::vector<Arc> edges = {{0, 4}, {6, 5}, {0, 2}, {2, 5}, {3, 6}, {1, 4}, {3, 1}, {0, 6}, {5, 4}};
    Decomposition undirected = undirected_edge_disjoint_paths(7, edges, 0, 6);
    std::cout << "  aristas canceladas: " << undirected.cancelled << '\n';
    print_decomposition(undirected, "sabcdet");

    std::cout << "\nCon una arista directa s -> t:\n";
    // s = 0, a = 1, b = 2, t = 3
    std::vector<Arc> adjacent = {{0, 3}, {0, 1}, {1, 3}, {0, 2}, {2, 3}};
    print_decomposition(vertex_disjoint_paths(4, adjacent, 0, 3), "sabt");
    SplitNetwork unlimited = split_network(4, adjacent, 0, 3, 5);
    std::cout << "  flujo si las aristas tienen capacidad \"sin límite\" (aquí, 5): "
              << unlimited.flow.edmonds_karp(unlimited.source, unlimited.sink) << '\n';
}

// Caminos disjuntos en aristas y en nodos, como flujo con capacidades 1.
#pragma once

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

#include "flow.h"

struct Arc {
    int from;
    int to;
};

struct Decomposition {
    std::vector<std::vector<int>> paths;
    std::vector<std::vector<int>> cycles;
    int cancelled = 0;  // aristas no dirigidas que el flujo usó en las dos direcciones
};

// Descompone un flujo entero en caminos simples de s a t y ciclos. flow_arcs tiene una entrada por cada
// unidad de flujo. Se camina por aristas sin usar: si se repite un nodo, lo recorrido desde su primera
// aparición es un ciclo y se aparta; si se llega a t, ahí hay un camino. La conservación impide atascarse.
inline Decomposition decompose_flow(int nodes, const std::vector<Arc>& flow_arcs, int s, int t) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    std::vector<std::vector<int>> out(at(nodes));
    int balance = 0;  // el valor del flujo: lo que sale de s menos lo que entra
    for (const Arc& arc : flow_arcs) {
        out[at(arc.from)].push_back(arc.to);
        if (arc.from == s) balance++;
        if (arc.to == s) balance--;
    }
    assert(balance >= 0);
    Decomposition result;
    std::vector<int> position(at(nodes), -1);

    // Camina desde start. Se detiene en stop, o si stop es -1, cuando un ciclo la devuelve a start.
    auto walk = [&](int start, int stop) {
        std::vector<int> trail = {start};
        position[at(start)] = 0;
        while (true) {
            int v = trail.back();
            if (v == stop) {
                for (int u : trail) position[at(u)] = -1;
                result.paths.push_back(trail);
                return;
            }
            assert(!out[at(v)].empty());  // lo garantiza la conservación
            int w = out[at(v)].back();
            out[at(v)].pop_back();
            if (position[at(w)] >= 0) {
                std::vector<int> cycle(trail.begin() + position[at(w)], trail.end());
                cycle.push_back(w);
                result.cycles.push_back(cycle);
                for (std::size_t k = at(position[at(w)]) + 1; k < trail.size(); k++) position[at(trail[k])] = -1;
                trail.resize(at(position[at(w)]) + 1);
                // Sin destino, se termina al volver al inicio: lo que queda en trail todavía no forma un ciclo.
                if (stop < 0 && trail.size() == 1) {
                    position[at(start)] = -1;
                    return;
                }
            } else {
                position[at(w)] = static_cast<int>(trail.size());
                trail.push_back(w);
            }
        }
    };

    for (int k = 0; k < balance; k++) walk(s, t);
    // Lo que queda está balanceado en todos los nodos: son solo ciclos.
    for (int v = 0; v < nodes; v++) {
        while (!out[at(v)].empty()) walk(v, -1);
    }
    return result;
}

// Dirigido: cada arista con capacidad 1.
inline Decomposition edge_disjoint_paths(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    MaxFlow flow(nodes);
    std::vector<int> ids;
    for (const Arc& arc : arcs) ids.push_back(flow.add_edge(arc.from, arc.to, 1));
    flow.edmonds_karp(s, t);
    std::vector<Arc> used;
    for (std::size_t k = 0; k < arcs.size(); k++) {
        if (flow.flow_on(ids[k]) == 1) used.push_back(arcs[k]);
    }
    return decompose_flow(nodes, used, s, t);
}

// No dirigido: cada arista son dos dirigidas de capacidad 1. Si el flujo usa las dos direcciones de una
// misma arista, se cancelan: siguen la conservación y el valor, y la arista queda libre.
inline Decomposition undirected_edge_disjoint_paths(int nodes, const std::vector<Arc>& edges, int s, int t) {
    MaxFlow flow(nodes);
    std::vector<std::pair<int, int>> ids;
    for (const Arc& edge : edges) {
        int forward = flow.add_edge(edge.from, edge.to, 1);
        int backward = flow.add_edge(edge.to, edge.from, 1);
        ids.emplace_back(forward, backward);
    }
    flow.edmonds_karp(s, t);
    std::vector<Arc> used;
    int cancelled = 0;
    for (std::size_t k = 0; k < edges.size(); k++) {
        long long forward = flow.flow_on(ids[k].first);
        long long backward = flow.flow_on(ids[k].second);
        if (forward == 1 && backward == 1) cancelled++;
        if (forward == 1 && backward == 0) used.push_back(edges[k]);
        if (forward == 0 && backward == 1) used.push_back({edges[k].to, edges[k].from});
    }
    Decomposition result = decompose_flow(nodes, used, s, t);
    result.cancelled = cancelled;
    return result;
}

// Corte mínimo con capacidades 1: las aristas que salen de lo alcanzable. Son las que hay que quitar.
inline std::vector<Arc> minimum_edge_cut(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    MaxFlow flow(nodes);
    for (const Arc& arc : arcs) flow.add_edge(arc.from, arc.to, 1);
    flow.edmonds_karp(s, t);
    std::vector<bool> reached = flow.reachable_from(s);
    std::vector<Arc> cut;
    for (const Arc& arc : arcs) {
        if (reached[static_cast<std::size_t>(arc.from)] && !reached[static_cast<std::size_t>(arc.to)]) cut.push_back(arc);
    }
    return cut;
}

// División de nodos. Cada nodo v distinto de s y t pasa a ser v_in = 2v y v_out = 2v + 1, unidos por
// una arista de capacidad 1. s y t no se dividen: usan un solo número, 2v + 1.
struct SplitNetwork {
    MaxFlow flow;
    std::vector<int> split_edge;  // la arista v_in → v_out de cada nodo, o -1 en s y t
    std::vector<int> arc_edge;    // la arista de la red de cada arista original
    int source;
    int sink;
};

// arc_capacity es la capacidad de las aristas originales. La de los nodos siempre es 1.
inline SplitNetwork split_network(int nodes, const std::vector<Arc>& arcs, int s, int t, long long arc_capacity) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    auto in = [&](int v) { return (v == s || v == t) ? 2 * v + 1 : 2 * v; };
    auto out = [](int v) { return 2 * v + 1; };
    SplitNetwork net{MaxFlow(2 * nodes), std::vector<int>(at(nodes), -1), {}, 2 * s + 1, 2 * t + 1};
    for (int v = 0; v < nodes; v++) {
        if (v != s && v != t) net.split_edge[at(v)] = net.flow.add_edge(in(v), out(v), 1);
    }
    for (const Arc& arc : arcs) net.arc_edge.push_back(net.flow.add_edge(out(arc.from), in(arc.to), arc_capacity));
    return net;
}

// Máximo de caminos que no comparten nodos internos. Una arista directa s → t cuenta como un camino.
inline Decomposition vertex_disjoint_paths(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    SplitNetwork net = split_network(nodes, arcs, s, t, 1);
    net.flow.edmonds_karp(net.source, net.sink);
    std::vector<Arc> used;
    for (std::size_t k = 0; k < arcs.size(); k++) {
        if (net.flow.flow_on(net.arc_edge[k]) == 1) used.push_back(arcs[k]);
    }
    return decompose_flow(nodes, used, s, t);
}

// Separador mínimo, leído del corte. Solo tiene sentido si no hay arista directa s → t.
inline std::vector<int> minimum_vertex_separator(int nodes, const std::vector<Arc>& arcs, int s, int t) {
    long long no_limit = nodes + 1;  // ningún corte que importe paga tanto: hay uno de a lo sumo V - 2
    SplitNetwork net = split_network(nodes, arcs, s, t, no_limit);
    net.flow.edmonds_karp(net.source, net.sink);
    std::vector<bool> reached = net.flow.reachable_from(net.source);
    std::vector<int> separator;
    for (int v = 0; v < nodes; v++) {
        if (v != s && v != t && reached[static_cast<std::size_t>(2 * v)] &&
            !reached[static_cast<std::size_t>(2 * v + 1)]) {
            separator.push_back(v);
        }
    }
    return separator;
}

// ¿Se llega de s a t sin pasar por lo prohibido?
inline bool connected_without(int nodes, const std::vector<Arc>& arcs, int s, int t,
                              const std::vector<bool>& node_removed, const std::vector<bool>& arc_removed) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    std::vector<bool> seen(at(nodes), false);
    std::vector<int> pending = {s};
    seen[at(s)] = true;
    while (!pending.empty()) {
        int v = pending.back();
        pending.pop_back();
        for (std::size_t k = 0; k < arcs.size(); k++) {
            if (!arc_removed[k] && arcs[k].from == v && !seen[at(arcs[k].to)] && !node_removed[at(arcs[k].to)]) {
                seen[at(arcs[k].to)] = true;
                pending.push_back(arcs[k].to);
            }
        }
    }
    return seen[at(t)];
}

// Flujo máximo: la clase que se usa en todo el capítulo. Las aristas se guardan en pares: la arista
// e y su inversa e ^ 1, que nace con capacidad 0. Guardar la capacidad que queda es guardar la red
// residual.
#pragma once

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <queue>
#include <vector>

class MaxFlow {
public:
    explicit MaxFlow(int nodes) : adjacency_(static_cast<std::size_t>(nodes)) {}

    // Devuelve el número de la arista, para preguntar después cuánto flujo lleva.
    int add_edge(int from, int to, long long capacity) {
        assert(capacity >= 0);
        int id = static_cast<int>(arcs_.size());
        arcs_.push_back({to, capacity});
        arcs_.push_back({from, 0});
        adjacency_[index(from)].push_back(id);
        adjacency_[index(to)].push_back(id + 1);
        return id;
    }

    // Camino de aumento con menos aristas, hallado con BFS. Se detiene apenas llega a t.
    long long edmonds_karp(int s, int t) {
        long long total = 0;
        while (true) {
            std::vector<int> arrived_by(adjacency_.size(), -1);
            std::vector<bool> seen(adjacency_.size(), false);
            std::queue<int> pending;
            seen[index(s)] = true;
            pending.push(s);
            while (!pending.empty() && !seen[index(t)]) {
                int v = pending.front();
                pending.pop();
                for (int id : adjacency_[index(v)]) {
                    const Arc& arc = arcs_[index(id)];
                    if (arc.residual > 0 && !seen[index(arc.to)]) {
                        seen[index(arc.to)] = true;
                        arrived_by[index(arc.to)] = id;
                        pending.push(arc.to);
                    }
                }
            }
            if (!seen[index(t)]) return total;
            total += push_along(arrived_by, s, t);
        }
    }

    // Camino de aumento cualquiera, el primero que encuentra un DFS.
    long long ford_fulkerson(int s, int t) {
        long long total = 0;
        while (true) {
            std::vector<int> arrived_by(adjacency_.size(), -1);
            std::vector<bool> seen(adjacency_.size(), false);
            std::vector<int> pending = {s};
            seen[index(s)] = true;
            while (!pending.empty() && !seen[index(t)]) {
                int v = pending.back();
                pending.pop_back();
                for (int id : adjacency_[index(v)]) {
                    const Arc& arc = arcs_[index(id)];
                    if (arc.residual > 0 && !seen[index(arc.to)]) {
                        seen[index(arc.to)] = true;
                        arrived_by[index(arc.to)] = id;
                        pending.push_back(arc.to);
                    }
                }
            }
            if (!seen[index(t)]) return total;
            total += push_along(arrived_by, s, t);
        }
    }

    // Lo alcanzable desde s en la red residual. Al terminar el flujo, es el lado de s de un corte mínimo.
    std::vector<bool> reachable_from(int s) const {
        std::vector<bool> seen(adjacency_.size(), false);
        std::vector<int> pending = {s};
        seen[index(s)] = true;
        while (!pending.empty()) {
            int v = pending.back();
            pending.pop_back();
            for (int id : adjacency_[index(v)]) {
                const Arc& arc = arcs_[index(id)];
                if (arc.residual > 0 && !seen[index(arc.to)]) {
                    seen[index(arc.to)] = true;
                    pending.push_back(arc.to);
                }
            }
        }
        return seen;
    }

    // El flujo de una arista es lo que su inversa puede devolver.
    long long flow_on(int id) const { return arcs_[index(id ^ 1)].residual; }

    // Cuánta capacidad le queda a una arista.
    long long left_on(int id) const { return arcs_[index(id)].residual; }

    // Quita una arista de la red, junto con lo que deshacerla permitiría.
    void remove_edge(int id) {
        arcs_[index(id)].residual = 0;
        arcs_[index(id ^ 1)].residual = 0;
    }

    int augmentations() const { return augmentations_; }

    // Los caminos de aumento usados, si se pidió guardarlos.
    void keep_paths() { keep_paths_ = true; }
    const std::vector<std::vector<int>>& paths() const { return paths_; }

private:
    struct Arc {
        int to;
        long long residual;
    };

    static std::size_t index(int i) { return static_cast<std::size_t>(i); }

    long long push_along(const std::vector<int>& arrived_by, int s, int t) {
        long long amount = std::numeric_limits<long long>::max();
        std::vector<int> path = {t};
        for (int v = t; v != s; v = arcs_[index(arrived_by[index(v)] ^ 1)].to) {
            amount = std::min(amount, arcs_[index(arrived_by[index(v)])].residual);
            path.push_back(arcs_[index(arrived_by[index(v)] ^ 1)].to);
        }
        for (int v = t; v != s; v = arcs_[index(arrived_by[index(v)] ^ 1)].to) {
            int id = arrived_by[index(v)];
            arcs_[index(id)].residual -= amount;
            arcs_[index(id ^ 1)].residual += amount;
        }
        augmentations_++;
        if (keep_paths_) {
            std::reverse(path.begin(), path.end());
            paths_.push_back(path);
        }
        return amount;
    }

    std::vector<std::vector<int>> adjacency_;
    std::vector<Arc> arcs_;
    int augmentations_ = 0;
    bool keep_paths_ = false;
    std::vector<std::vector<int>> paths_;
};

// "Al menos dos de cada grupo" no es una capacidad. Tres modelos de la misma situación.
#include <iostream>
#include <vector>

#include "lower_bounds.h"

namespace {

// s = 0, A = 1, B = 2, T1 = 3, T2 = 4, t = 5
std::vector<BoundedEdge> network(long long low, long long high_group) {
    return {{0, 1, low, high_group}, {0, 2, low, high_group}, {1, 3, 0, 3}, {1, 4, 0, 1},
            {2, 4, 0, 2},            {3, 5, 0, 3},            {4, 5, 0, 2}};
}

void report(const BoundedFlow& result) {
    std::cout << "  total " << result.value << ", grupo A " << result.on_edge[0] << ", grupo B " << result.on_edge[1] << '\n';
}

}  // namespace

int main() {
    std::cout << "Grupo A: 4 personas. Grupo B: 2 personas. Turnos: T1 con cupo 3, T2 con cupo 2.\n";
    std::cout << "A puede ir a T1 (hasta 3) o a T2 (1). B solo puede ir a T2.\n\n";

    std::cout << "Sin restricción:\n";
    report(max_flow_with_lower_bounds(6, network(0, 4), 0, 5));

    std::cout << "Capacidad 2 en s -> grupo, que significa \"a lo sumo dos\":\n";
    report(max_flow_with_lower_bounds(6, network(0, 2), 0, 5));

    std::cout << "Cota inferior 2 en s -> grupo:\n";
    report(max_flow_with_lower_bounds(6, network(2, 4), 0, 5));
    std::cout << "  fuerza bruta: " << brute_bounded(6, network(2, 4), 0, 5) << '\n';

    std::cout << "\nSi B pudiera aportar solo por T2 y T2 tuviera cupo 1, no hay solución:\n";
    std::vector<BoundedEdge> impossible = network(2, 4);
    impossible[6].high = 1;
    BoundedFlow none = max_flow_with_lower_bounds(6, impossible, 0, 5);
    std::cout << "  factible: " << (none.feasible ? "sí" : "no") << ", fuerza bruta: " << brute_bounded(6, impossible, 0, 5) << '\n';
}

// Flujo con cotas inferiores: cada arista debe llevar entre low y high.
#pragma once

#include <cassert>
#include <cstddef>
#include <vector>

#include "flow.h"

struct BoundedEdge {
    int from;
    int to;
    long long low;
    long long high;
};

struct BoundedFlow {
    bool feasible = false;
    long long value = 0;
    std::vector<long long> on_edge;
};

// La transformación: cada arista queda con capacidad high - low, y las low unidades obligatorias se piden
// con una fuente y un sumidero nuevos. Con la arista t → s, buscar un flujo factible se vuelve un flujo
// máximo que debe saturar la nueva fuente. Después se quita t → s y se aumenta de s a t.
inline BoundedFlow max_flow_with_lower_bounds(int nodes, const std::vector<BoundedEdge>& edges, int s, int t) {
    int new_source = nodes;
    int new_sink = nodes + 1;
    MaxFlow flow(nodes + 2);
    std::vector<int> ids;
    long long required = 0;
    long long no_limit = 1;
    for (const BoundedEdge& e : edges) no_limit += e.high;
    for (const BoundedEdge& e : edges) {
        assert(0 <= e.low && e.low <= e.high);
        ids.push_back(flow.add_edge(e.from, e.to, e.high - e.low));
        if (e.low > 0) {
            flow.add_edge(new_source, e.to, e.low);
            flow.add_edge(e.from, new_sink, e.low);
            required += e.low;
        }
    }
    int back = flow.add_edge(t, s, no_limit);
    BoundedFlow result;
    if (flow.edmonds_karp(new_source, new_sink) < required) return result;
    result.feasible = true;
    long long first_part = flow.flow_on(back);
    flow.remove_edge(back);
    result.value = first_part + flow.edmonds_karp(s, t);
    for (std::size_t k = 0; k < edges.size(); k++) result.on_edge.push_back(edges[k].low + flow.flow_on(ids[k]));
    return result;
}

// Árbitro: prueba todos los valores de todas las aristas. Devuelve -1 si no hay flujo factible.
inline long long brute_bounded(int nodes, const std::vector<BoundedEdge>& edges, int s, int t) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    std::vector<long long> net(at(nodes), 0);
    long long best = -1;
    auto search = [&](auto&& self, std::size_t k) -> void {
        if (k == edges.size()) {
            for (int v = 0; v < nodes; v++) {
                if (v != s && v != t && net[at(v)] != 0) return;
            }
            if (net[at(s)] > best) best = net[at(s)];
            return;
        }
        for (long long x = edges[k].low; x <= edges[k].high; x++) {
            net[at(edges[k].from)] += x;
            net[at(edges[k].to)] -= x;
            self(self, k + 1);
            net[at(edges[k].from)] -= x;
            net[at(edges[k].to)] += x;
        }
    };
    search(search, 0);
    return best;
}

// Cuánto cuesta el matching como flujo: aumentos y tiempo, con grafos al azar de grado fijo. Se compila con -O2.
#include <chrono>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

#include "matching.h"

namespace {

Options random_options(int n, int degree, std::uint32_t seed) {
    std::mt19937 random(seed);
    Options options(static_cast<std::size_t>(n));
    for (auto& list : options) {
        for (int k = 0; k < degree; k++) {
            int j = static_cast<int>(random() % static_cast<std::uint32_t>(n));
            if (std::find(list.begin(), list.end(), j) == list.end()) list.push_back(j);
        }
    }
    return options;
}

}  // namespace

int main() {
    std::cout << "     n   aristas  matching  aumentos EK  ms EK  aumentos DFS  ms DFS\n";
    for (int n : {2000, 4000, 8000, 16000, 32000}) {
        Options options = random_options(n, 3, 12345);
        std::size_t edges = 0;
        for (const auto& list : options) edges += list.size();
        MatchingNetwork bfs = matching_network(options, n);
        auto start = std::chrono::steady_clock::now();
        long long value = bfs.flow.edmonds_karp(bfs.source, bfs.sink);
        auto middle = std::chrono::steady_clock::now();
        MatchingNetwork dfs = matching_network(options, n);
        auto middle2 = std::chrono::steady_clock::now();
        long long value2 = dfs.flow.ford_fulkerson(dfs.source, dfs.sink);
        auto end = std::chrono::steady_clock::now();
        assert(value == value2);
        std::cout.width(6);
        std::cout << n;
        std::cout.width(10);
        std::cout << edges;
        std::cout.width(10);
        std::cout << value;
        std::cout.width(13);
        std::cout << bfs.flow.augmentations();
        std::cout.width(7);
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(middle - start).count();
        std::cout.width(14);
        std::cout << dfs.flow.augmentations();
        std::cout.width(8);
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - middle2).count() << '\n';
    }
}

// Matching bipartito: la red, los caminos de aumento, los greedy que fallan y la capacidad que no se puede olvidar.
#include <iostream>
#include <string>
#include <vector>

#include "matching.h"

namespace {

std::string node_name(int v, int left, int sink) {
    if (v == 0) return "s";
    if (v == sink) return "t";
    if (v <= left) return "E" + std::to_string(v - 1);
    return "S" + std::to_string(v - left - 1);
}

void print_options(const Options& options) {
    for (std::size_t i = 0; i < options.size(); i++) {
        std::cout << "  E" << i << ":";
        for (int j : options[i]) std::cout << " S" << j;
        std::cout << '\n';
    }
}

void print_matching(const std::vector<int>& partner) {
    std::cout << assigned_count(partner) << " (";
    bool first = true;
    for (std::size_t i = 0; i < partner.size(); i++) {
        if (partner[i] < 0) continue;
        std::cout << (first ? "" : ", ") << "E" << i << "-S" << partner[i];
        first = false;
    }
    std::cout << ")\n";
}

void run_network(const Options& options, int right) {
    int left = static_cast<int>(options.size());
    MatchingNetwork net = matching_network(options, right);
    net.flow.keep_paths();
    long long value = net.flow.edmonds_karp(net.source, net.sink);
    for (const auto& path : net.flow.paths()) {
        std::cout << "  camino:";
        for (int v : path) std::cout << ' ' << node_name(v, left, net.sink);
        std::cout << '\n';
    }
    std::cout << "  flujo máximo: " << value << '\n';
    std::cout << "  matching: ";
    print_matching(read_matching(net, options));
}

void compare_greedy(const Options& options, int right) {
    std::vector<int> quota(static_cast<std::size_t>(right), 1);
    std::vector<int> copy = quota;
    std::cout << "  primera opción libre:        ";
    print_matching(first_fit(options, quota));
    std::cout << "  menos opciones primero:      ";
    print_matching(fewest_options_first(options, quota));
    std::cout << "  óptimo por fuerza bruta:     " << brute_assignment(options, copy) << '\n';
    std::cout << "  flujo:                       ";
    print_matching(max_matching(options, right));
}

}  // namespace

int main() {
    std::cout << "Una red de 3 por 3:\n";
    Options three = {{0, 1}, {0}, {1, 2}};
    print_options(three);
    run_network(three, 3);

    std::cout << "\nCada uno a su primera opción libre falla:\n";
    Options first = {{0, 1}, {0}};
    print_options(first);
    compare_greedy(first, 2);

    std::cout << "\nMenos opciones primero también falla:\n";
    Options fewest = {{0, 1}, {2, 0}, {2}};
    print_options(fewest);
    compare_greedy(fewest, 3);

    std::cout << "\nSin el límite en s -> estudiante, E0 cuenta dos veces:\n";
    Options greedy_student = {{0, 1}, {}};
    print_options(greedy_student);
    MatchingNetwork wide = matching_network(greedy_student, 2, 1000);
    std::cout << "  flujo con capacidad 1000 en s -> E: " << wide.flow.edmonds_karp(wide.source, wide.sink) << '\n';
    std::vector<int> quota = {1, 1};
    std::cout << "  matching máximo real:               " << brute_assignment(greedy_student, quota) << '\n';
}