// Kruskal contra Prim con grafos al azar conexos, compilado con -O2. Toma el menor de 3 intentos.
// Las entradas y descartes de la cola no dependen de la máquina; los tiempos sí.
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "mst.h"

namespace {

std::vector<Edge> random_connected(int n, int m, unsigned seed) {
    std::mt19937 rng(seed);
    std::vector<Edge> edges;
    edges.reserve(static_cast<std::size_t>(m));
    for (int v = 1; v < n; v++) {
        edges.push_back({static_cast<int>(rng() % static_cast<unsigned>(v)), v, static_cast<int>(rng() % 1000000000U)});
    }
    while (static_cast<int>(edges.size()) < m) {
        int a = static_cast<int>(rng() % static_cast<unsigned>(n));
        int b = static_cast<int>(rng() % static_cast<unsigned>(n));
        if (a != b) edges.push_back({a, b, static_cast<int>(rng() % 1000000000U)});
    }
    return edges;
}

template <typename Run>
double best_ms(Run run) {
    double best = 1e18;
    for (int attempt = 0; attempt < 3; attempt++) {
        auto begin = std::chrono::steady_clock::now();
        run();
        auto end = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(end - begin).count());
    }
    return best;
}

}  // namespace

int main() {
    std::printf("%8s %9s %11s %9s %11s %10s %10s\n", "V", "E", "kruskal ms", "prim ms", "entradas", "descartes", "costo igual");
    for (auto [n, m] : std::vector<std::pair<int, int>>{{50000, 200000}, {200000, 800000}, {800000, 3200000},
                                                        {100000, 3200000}, {3000, 3200000}}) {
        std::vector<Edge> edges = random_connected(n, m, 2026);
        long long kruskal_cost = 0;
        long long prim_cost = 0;
        long long pushes = 0;
        long long stale = 0;
        double k_ms = best_ms([&] { kruskal_cost = total_weight(kruskal(n, edges)); });
        double p_ms = best_ms([&] {
            PrimResult result = prim(n, edges, 0);
            prim_cost = total_weight(result.tree);
            pushes = result.pushes;
            stale = result.stale_pops;
        });
        std::printf("%8d %9d %11.1f %9.1f %11lld %10lld %10s\n", n, m, k_ms, p_ms, pushes, stale,
                    kruskal_cost == prim_cost ? "sí" : "NO");
    }
}