// Selección de proyectos: elegir un conjunto cerrado por prerrequisitos con la mayor ganancia total.
#pragma once

#include <cassert>
#include <cstddef>
#include <vector>

#include "flow.h"

struct Requirement {
    int project;
    int needs;
};

struct ProjectChoice {
    long long value = 0;
    long long min_cut = 0;
    long long positive_total = 0;
    std::vector<int> chosen;
};

// profit[i] > 0 es una ganancia, profit[i] < 0 un costo. prerequisite_capacity = -1 usa el "infinito"
// de la reducción. Se deja como parámetro para ver qué pasa con una capacidad finita.
inline ProjectChoice best_projects(const std::vector<long long>& profit, const std::vector<Requirement>& requires_list,
                                   long long prerequisite_capacity = -1) {
    int n = static_cast<int>(profit.size());
    int source = n;
    int sink = n + 1;
    ProjectChoice result;
    long long negative_total = 0;
    for (long long p : profit) {
        if (p > 0) result.positive_total += p;
        if (p < 0) negative_total -= p;
    }
    // El corte {s} ya cuesta positive_total. Una arista más cara que eso nunca está en un corte mínimo.
    long long infinity = result.positive_total + 1;
    assert(negative_total >= 0);
    MaxFlow flow(n + 2);
    for (int i = 0; i < n; i++) {
        long long p = profit[static_cast<std::size_t>(i)];
        if (p > 0) flow.add_edge(source, i, p);
        if (p < 0) flow.add_edge(i, sink, -p);
    }
    for (const Requirement& r : requires_list) {
        flow.add_edge(r.project, r.needs, prerequisite_capacity < 0 ? infinity : prerequisite_capacity);
    }
    result.min_cut = flow.edmonds_karp(source, sink);
    result.value = result.positive_total - result.min_cut;
    std::vector<bool> reached = flow.reachable_from(source);
    for (int i = 0; i < n; i++) {
        if (reached[static_cast<std::size_t>(i)]) result.chosen.push_back(i);
    }
    return result;
}

inline long long total_profit(const std::vector<long long>& profit, const std::vector<int>& chosen) {
    long long total = 0;
    for (int i : chosen) total += profit[static_cast<std::size_t>(i)];
    return total;
}

inline bool is_closed(int n, const std::vector<Requirement>& requires_list, const std::vector<int>& chosen) {
    std::vector<bool> in(static_cast<std::size_t>(n), false);
    for (int i : chosen) in[static_cast<std::size_t>(i)] = true;
    for (const Requirement& r : requires_list) {
        if (in[static_cast<std::size_t>(r.project)] && !in[static_cast<std::size_t>(r.needs)]) return false;
    }
    return true;
}

// Árbitro: prueba los 2ⁿ subconjuntos.
inline long long brute_projects(const std::vector<long long>& profit, const std::vector<Requirement>& requires_list) {
    int n = static_cast<int>(profit.size());
    long long best = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        std::vector<int> chosen;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1u) chosen.push_back(i);
        }
        if (is_closed(n, requires_list, chosen)) best = std::max(best, total_profit(profit, chosen));
    }
    return best;
}

// Greedy: tomar un proyecto con su cadena de prerrequisitos solo si ese paquete, por sí solo, deja ganancia.
// Lo que ya se tomó no se vuelve a pagar.
inline std::vector<int> greedy_packages(const std::vector<long long>& profit, const std::vector<Requirement>& requires_list) {
    int n = static_cast<int>(profit.size());
    std::vector<bool> taken(static_cast<std::size_t>(n), false);
    for (int i = 0; i < n; i++) {
        std::vector<bool> package = taken;
        std::vector<int> pending = {i};
        package[static_cast<std::size_t>(i)] = true;
        while (!pending.empty()) {
            int v = pending.back();
            pending.pop_back();
            for (const Requirement& r : requires_list) {
                if (r.project == v && !package[static_cast<std::size_t>(r.needs)]) {
                    package[static_cast<std::size_t>(r.needs)] = true;
                    pending.push_back(r.needs);
                }
            }
        }
        long long gain = 0;
        for (int k = 0; k < n; k++) {
            if (package[static_cast<std::size_t>(k)] && !taken[static_cast<std::size_t>(k)]) gain += profit[static_cast<std::size_t>(k)];
        }
        if (gain > 0) taken = package;
    }
    std::vector<int> chosen;
    for (int i = 0; i < n; i++) {
        if (taken[static_cast<std::size_t>(i)]) chosen.push_back(i);
    }
    return chosen;
}