// 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';
}