// Flujo con cotas inferiores: cada arista debe llevar entre low y high.
#pragma once

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

#include "flow.h"

struct BoundedEdge {
    int from;
    int to;
    long long low;
    long long high;
};

struct BoundedFlow {
    bool feasible = false;
    long long value = 0;
    std::vector<long long> on_edge;
};

// La transformación: cada arista queda con capacidad high - low, y las low unidades obligatorias se piden
// con una fuente y un sumidero nuevos. Con la arista t → s, buscar un flujo factible se vuelve un flujo
// máximo que debe saturar la nueva fuente. Después se quita t → s y se aumenta de s a t.
inline BoundedFlow max_flow_with_lower_bounds(int nodes, const std::vector<BoundedEdge>& edges, int s, int t) {
    int new_source = nodes;
    int new_sink = nodes + 1;
    MaxFlow flow(nodes + 2);
    std::vector<int> ids;
    long long required = 0;
    long long no_limit = 1;
    for (const BoundedEdge& e : edges) no_limit += e.high;
    for (const BoundedEdge& e : edges) {
        assert(0 <= e.low && e.low <= e.high);
        ids.push_back(flow.add_edge(e.from, e.to, e.high - e.low));
        if (e.low > 0) {
            flow.add_edge(new_source, e.to, e.low);
            flow.add_edge(e.from, new_sink, e.low);
            required += e.low;
        }
    }
    int back = flow.add_edge(t, s, no_limit);
    BoundedFlow result;
    if (flow.edmonds_karp(new_source, new_sink) < required) return result;
    result.feasible = true;
    long long first_part = flow.flow_on(back);
    flow.remove_edge(back);
    result.value = first_part + flow.edmonds_karp(s, t);
    for (std::size_t k = 0; k < edges.size(); k++) result.on_edge.push_back(edges[k].low + flow.flow_on(ids[k]));
    return result;
}

// Árbitro: prueba todos los valores de todas las aristas. Devuelve -1 si no hay flujo factible.
inline long long brute_bounded(int nodes, const std::vector<BoundedEdge>& edges, int s, int t) {
    auto at = [](int i) { return static_cast<std::size_t>(i); };
    std::vector<long long> net(at(nodes), 0);
    long long best = -1;
    auto search = [&](auto&& self, std::size_t k) -> void {
        if (k == edges.size()) {
            for (int v = 0; v < nodes; v++) {
                if (v != s && v != t && net[at(v)] != 0) return;
            }
            if (net[at(s)] > best) best = net[at(s)];
            return;
        }
        for (long long x = edges[k].low; x <= edges[k].high; x++) {
            net[at(edges[k].from)] += x;
            net[at(edges[k].to)] -= x;
            self(self, k + 1);
            net[at(edges[k].from)] -= x;
            net[at(edges[k].to)] += x;
        }
    };
    search(search, 0);
    return best;
}