// Matching bipartito como flujo, y las ideas parecidas que no alcanzan.
// options[i] son los nodos de la derecha que admite el nodo i de la izquierda.
#pragma once

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <vector>

#include "flow.h"

using Options = std::vector<std::vector<int>>;

inline std::size_t at(int i) { return static_cast<std::size_t>(i); }

// La red de la reducción. Numeración: s = 0, izquierda 1..L, derecha L+1..L+R, t = L+R+1.
struct MatchingNetwork {
    MaxFlow flow;
    int source;
    int sink;
    std::vector<std::vector<int>> middle;  // el número de cada arista izquierda → derecha
};

// source_capacity es 1 en la reducción correcta. Se deja como parámetro para ver qué pasa sin ese límite.
inline MatchingNetwork matching_network(const Options& options, int right, long long source_capacity = 1) {
    int left = static_cast<int>(options.size());
    MatchingNetwork net{MaxFlow(left + right + 2), 0, left + right + 1, {}};
    for (int i = 0; i < left; i++) net.flow.add_edge(net.source, 1 + i, source_capacity);
    for (int j = 0; j < right; j++) net.flow.add_edge(1 + left + j, net.sink, 1);
    for (int i = 0; i < left; i++) {
        net.middle.emplace_back();
        for (int j : options[at(i)]) net.middle.back().push_back(net.flow.add_edge(1 + i, 1 + left + j, 1));
    }
    return net;
}

// Un flujo entero se lee como matching: las aristas del medio que llevan 1.
inline std::vector<int> read_matching(const MatchingNetwork& net, const Options& options) {
    std::vector<int> partner(options.size(), -1);
    for (std::size_t i = 0; i < options.size(); i++) {
        for (std::size_t k = 0; k < options[i].size(); k++) {
            if (net.flow.flow_on(net.middle[i][k]) == 1) partner[i] = options[i][k];
        }
    }
    return partner;
}

// Devuelve la pareja de cada nodo de la izquierda, o -1.
inline std::vector<int> max_matching(const Options& options, int right) {
    MatchingNetwork net = matching_network(options, right);
    net.flow.edmonds_karp(net.source, net.sink);
    return read_matching(net, options);
}

inline int assigned_count(const std::vector<int>& partner) {
    int count = 0;
    for (int p : partner) count += p >= 0;
    return count;
}

// ¿Es un matching de verdad? Cada pareja permitida, y nadie de la derecha repetido.
inline bool is_matching(const Options& options, int right, const std::vector<int>& partner) {
    std::vector<int> used(at(right), 0);
    for (std::size_t i = 0; i < options.size(); i++) {
        if (partner[i] < 0) continue;
        if (std::find(options[i].begin(), options[i].end(), partner[i]) == options[i].end()) return false;
        if (++used[at(partner[i])] > 1) return false;
    }
    return true;
}

// Greedy 1: cada uno, en orden, a su primera opción con cupo.
inline std::vector<int> first_fit(const Options& options, std::vector<int> quota) {
    std::vector<int> partner(options.size(), -1);
    for (std::size_t i = 0; i < options.size(); i++) {
        for (int j : options[i]) {
            if (quota[at(j)] > 0) {
                quota[at(j)]--;
                partner[i] = j;
                break;
            }
        }
    }
    return partner;
}

// Greedy 2: primero el que tiene menos opciones en la entrada, sin recalcular, y luego igual que el anterior.
inline std::vector<int> fewest_options_first(const Options& options, std::vector<int> quota) {
    std::vector<std::size_t> order(options.size());
    std::iota(order.begin(), order.end(), std::size_t{0});
    std::stable_sort(order.begin(), order.end(),
                     [&](std::size_t a, std::size_t b) { return options[a].size() < options[b].size(); });
    std::vector<int> partner(options.size(), -1);
    for (std::size_t i : order) {
        for (int j : options[i]) {
            if (quota[at(j)] > 0) {
                quota[at(j)]--;
                partner[i] = j;
                break;
            }
        }
    }
    return partner;
}

// Fuerza bruta: cada uno de la izquierda se queda sin nada o toma una opción con cupo. Es el árbitro.
inline int brute_assignment(const Options& options, std::vector<int>& quota, std::size_t i = 0) {
    if (i == options.size()) return 0;
    int best = brute_assignment(options, quota, i + 1);
    for (int j : options[i]) {
        if (quota[at(j)] > 0) {
            quota[at(j)]--;
            best = std::max(best, 1 + brute_assignment(options, quota, i + 1));
            quota[at(j)]++;
        }
    }
    return best;
}