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