Максимальная передача энергии и узкое место сетиMaximum power transfer and the grid's bottleneck

Дана сеть из n узлов (подстанций, пронумерованы 0..n-1), электростанция — узел 0, город-потребитель — узел n-1. Список `lines[i] = [a, b, capacity]` — линия передачи между a и b с максимальной пропускной мощностью `capacity` (передача возможна в обе стороны, но не более `capacity` суммарно в любой момент). Нужно найти максимальную мощность, которую можно передать от электростанции к городу, и список линий, образующих узкое место (минимальный разрез) — расширение которых первым увеличило бы общую пропускную способность сети.Given a network of n nodes (substations, numbered 0..n-1), the power plant is node 0, the consumer city is node n-1. The list `lines[i] = [a, b, capacity]` gives a transmission line between a and b with maximum capacity `capacity` (transfer works both ways, but no more than `capacity` total at any moment). Find the maximum power transferable from the plant to the city, and the list of lines forming the bottleneck (the minimum cut) — the ones that, if upgraded first, would raise the network's overall capacity.

// Example
n = 4  // 0=станция, 3=город// 0=plant, 3=city
lines = [[0,1,3],[0,2,2],[1,3,2],[2,3,3],[1,2,1]]
// output: max_power=5, bottleneck=[[0,1,3], [0,2,2]]

Прямая проекция терминологии 3.3.1 на условие: подстанции — вершины, линии передачи с пропускной способностью — рёбра с capacity, электростанция — источник s, город — сток t. "Максимальная передаваемая мощность" — это буквально величина максимального потока. Решаем через Эдмондса-Карпа (BFS для поиска кратчайшего увеличивающего пути в остаточной сети, как рекомендовано в 3.3.1 вместо наивного Форда-Фалкерсона).A direct mapping of 3.3.1's terminology onto the problem: substations are vertices, transmission lines with capacity are capacity-weighted edges, the plant is the source s, the city is the sink t. "Maximum transferable power" is literally the maximum flow's value. We solve it via Edmonds-Karp (BFS to find the shortest augmenting path in the residual graph, as 3.3.1 recommends over naive Ford-Fulkerson).

После того как Эдмондс-Карп находит величину максимального потока, минимальный разрез восстанавливается ровно так, как описано в 3.3.1: запускаем финальный BFS/DFS в остаточной сети от источника s и смотрим, какие вершины всё ещё достижимы (это множество S), а какие — нет (множество T = остальные). Рёбра исходного графа, идущие из S в T, — это и есть рёбра минимального разреза; по теореме о максимальном потоке и минимальном разрезе, сумма их пропускных способностей равна найденной величине потока.Once Edmonds-Karp finds the max flow's value, the minimum cut is recovered exactly as described in 3.3.1: run a final BFS/DFS on the residual graph from source s, and see which vertices are still reachable (set S) and which aren't (set T = the rest). The original graph's edges going from S to T are exactly the minimum cut's edges; by the max-flow min-cut theorem, the sum of their capacities equals the flow value found.

class Solution {
    std::vector<std::vector<int>> cap;   // остаточная пропускная способность// residual capacity
    int n;

    bool bfs(int s, int t, std::vector<int>& parent) {
        std::fill(parent.begin(), parent.end(), -1);
        parent[s] = s;
        std::queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; ++v)
                if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; q.push(v); }
        }
        return parent[t] != -1;
    }

public:
    std::pair<int, std::vector<std::array<int,2>>>
    maxPowerAndBottleneck(int nodes, std::vector<std::array<int,3>>& lines) {
        n = nodes;
        cap.assign(n, std::vector<int>(n, 0));
        for (auto& l : lines) { cap[l[0]][l[1]] += l[2]; cap[l[1]][l[0]] += l[2]; }

        int s = 0, t = n - 1, maxFlow = 0;
        std::vector<int> parent(n);
        while (bfs(s, t, parent)) {              // Эдмондс-Карп: BFS ищет кратчайший путь// Edmonds-Karp: BFS finds the shortest path
            int pushed = INT_MAX;
            for (int v = t; v != s; v = parent[v])
                pushed = std::min(pushed, cap[parent[v]][v]);
            for (int v = t; v != s; v = parent[v]) {
                cap[parent[v]][v] -= pushed;
                cap[v][parent[v]] += pushed;          // обратное ребро для отката// reverse edge for undoing
            }
            maxFlow += pushed;
        }

        std::vector<bool> reachable(n, false);   // восстановление min-cut// recovering the min-cut
        std::queue<int> q; q.push(s); reachable[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; ++v)
                if (!reachable[v] && cap[u][v] > 0) { reachable[v] = true; q.push(v); }
        }

        std::vector<std::array<int,2>> bottleneck;
        for (auto& l : lines)
            if (reachable[l[0]] != reachable[l[1]])   // ребро пересекает S/T// edge crosses S/T
                bottleneck.push_back({l[0], l[1]});

        return {maxFlow, bottleneck};
    }
};

Сложность O(VE²) — стандартная гарантия Эдмондса-Карпа из 3.3.1. Восстановление разреза — дополнительный BFS/DFS O(V+E) поверх уже посчитанной остаточной сети, а не отдельный алгоритм: сеть после завершения потокового алгоритма уже "знает" ответ, нужно лишь один раз проверить достижимость.Complexity is O(VE²) — the standard Edmonds-Karp guarantee from 3.3.1. Recovering the cut is an extra O(V+E) BFS/DFS on top of the already-computed residual graph, not a separate algorithm: the network already "knows" the answer once the flow algorithm finishes, all that's left is a single reachability check.