// Asignación con cupos. Una red escrita a mano, arista por arista, para poder compararla con un dibujo.
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "matching.h"

namespace {

// Dos estudiantes quieren S0, que tiene cupo 1, y S1 queda libre: la pregunta de repaso.
void same_section(bool one_can_move) {
    // s = 0, E0 = 1, E1 = 2, S0 = 3, S1 = 4, t = 5
    MaxFlow flow(6);
    flow.add_edge(0, 1, 1);
    flow.add_edge(0, 2, 1);
    flow.add_edge(1, 3, 1);
    flow.add_edge(2, 3, 1);
    if (one_can_move) flow.add_edge(2, 4, 1);
    int to_sink_0 = flow.add_edge(3, 5, 1);
    int to_sink_1 = flow.add_edge(4, 5, 1);
    const std::vector<std::string> names = {"s", "E0", "E1", "S0", "S1", "t"};
    std::cout << "  flujo: " << flow.edmonds_karp(0, 5) << '\n';
    std::cout << "  S0 -> t lleva " << flow.flow_on(to_sink_0) << ", S1 -> t lleva " << flow.flow_on(to_sink_1) << '\n';
    std::vector<bool> reached = flow.reachable_from(0);
    std::cout << "  alcanzables desde s:";
    for (std::size_t v = 0; v < names.size(); v++) {
        if (reached[v]) std::cout << ' ' << names[v];
    }
    std::cout << '\n';
}

}  // namespace

int main() {
    const Options options = {{0}, {0}, {2, 1}, {0, 2}, {2}, {0}};
    const std::vector<int> quota = {2, 1, 2};
    std::cout << "Seis estudiantes y tres secciones, con cupos S0: 2, S1: 1, S2: 2\n";
    for (std::size_t i = 0; i < options.size(); i++) {
        std::cout << "  E" << i << ":";
        for (int j : options[i]) std::cout << " S" << j;
        std::cout << '\n';
    }

    std::vector<int> quota_copy = quota;
    std::cout << "\nLos greedy y el árbitro:\n";
    std::cout << "  primera opción libre:   " << assigned_count(first_fit(options, quota)) << '\n';
    std::cout << "  menos opciones primero: " << assigned_count(fewest_options_first(options, quota)) << '\n';
    std::cout << "  fuerza bruta:           " << brute_assignment(options, quota_copy) << '\n';

    // s = 0, E0..E5 = 1..6, S0..S2 = 7..9, t = 10
    MaxFlow flow(11);
    for (int e = 1; e <= 6; e++) flow.add_edge(0, e, 1);
    flow.add_edge(7, 10, 2);
    flow.add_edge(8, 10, 1);
    flow.add_edge(9, 10, 2);
    const std::vector<std::pair<int, int>> middle = {{0, 0}, {1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 2}, {4, 2}, {5, 0}};
    std::vector<int> ids;
    ids.push_back(flow.add_edge(1, 7, 1));
    ids.push_back(flow.add_edge(2, 7, 1));
    ids.push_back(flow.add_edge(3, 9, 1));
    ids.push_back(flow.add_edge(3, 8, 1));
    ids.push_back(flow.add_edge(4, 7, 1));
    ids.push_back(flow.add_edge(4, 9, 1));
    ids.push_back(flow.add_edge(5, 9, 1));
    ids.push_back(flow.add_edge(6, 7, 1));

    std::cout << "\nFlujo máximo: " << flow.edmonds_karp(0, 10) << " de 6\n";
    std::cout << "Aristas del medio con flujo:";
    for (std::size_t k = 0; k < middle.size(); k++) {
        if (flow.flow_on(ids[k]) == 1) std::cout << " E" << middle[k].first << "-S" << middle[k].second;
    }
    std::vector<bool> reached = flow.reachable_from(0);
    std::cout << "\nEstudiantes alcanzables desde s:";
    for (int e = 1; e <= 6; e++) {
        if (reached[static_cast<std::size_t>(e)]) std::cout << " E" << e - 1;
    }
    std::cout << "\nSecciones alcanzables desde s:";
    for (int j = 7; j <= 9; j++) {
        if (reached[static_cast<std::size_t>(j)]) std::cout << " S" << j - 7;
    }
    std::cout << "\n\nDos quieren S0, con cupo 1, y S1 queda libre porque ninguno puede ir:\n";
    same_section(false);
    std::cout << "Lo mismo, pero E1 también puede ir a S1:\n";
    same_section(true);
}