// 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();
}