// La reducción que descarta una aproximación sin desigualdad triangular. Si un algoritmo tuviera
// factor alfa = 2, comparar su largo con alfa·n decidiría si hay ciclo hamiltoniano.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "../week-10/held_karp.h"
#include "tour.h"

namespace {

using tour::at;
using EdgeList = std::vector<std::pair<int, int>>;

tour::Matrix weights_from_graph(int n, const EdgeList& edges, long long heavy) {
    tour::Matrix w(at(n), std::vector<long long>(at(n), heavy));
    for (int v = 0; v < n; v++) w[at(v)][at(v)] = 0;
    for (const auto& [u, v] : edges) w[at(u)][at(v)] = w[at(v)][at(u)] = 1;
    return w;
}

void show(const std::string& title, int n, const EdgeList& edges) {
    const int alpha = 2;
    const long long heavy = alpha * n + 1;
    const auto w = weights_from_graph(n, edges, heavy);
    const long long optimum = tsp::held_karp(w);
    const auto doubled = tour::double_tree(w);
    std::cout << title << '\n';
    std::cout << "  n = " << n << ", W = " << heavy << ", alfa·n = " << alpha * n << '\n';
    std::cout << "  óptimo: " << optimum << (optimum <= alpha * n ? " <= " : " > ") << alpha * n << '\n';
    std::cout << "  árbol duplicado:";
    for (int v : doubled) std::cout << ' ' << v;
    std::cout << ", largo " << tour::tour_length(w, doubled) << "\n\n";
}

}  // namespace

int main() {
    show("Un ciclo de 6 nodos con la numeración desordenada: sí hay ciclo hamiltoniano", 6,
         {{0, 3}, {3, 1}, {1, 5}, {5, 2}, {2, 4}, {4, 0}});
    show("Dos nodos unidos a otros cuatro, K(2,4): no hay ciclo hamiltoniano", 6,
         {{0, 2}, {0, 3}, {0, 4}, {0, 5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}});
}