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