Разбор задачи «Минимизация пиковой нагрузки энергосети»

Идея задачи

Даны N станций, у каждой есть начальная нагрузка. Также даны M связей между станциями. Если между станциями есть путь, то внутри такой связной компоненты нагрузку можно перераспределять.

Нужно найти минимально возможное значение максимальной нагрузки на одной станции после всех допустимых перераспределений.

Ключевое наблюдение

Если две станции находятся в одной связной компоненте, то нагрузку можно передавать по пути между ними. Значит, внутри одной связной компоненты суммарную нагрузку можно считать общей.

Тогда задача распадается на независимые подзадачи по компонентам связности.

Для каждой компоненты важно знать только:

• sum — суммарную нагрузку в компоненте,
• size — число вершин в компоненте.

Дальше возникает вопрос:

можно ли сделать так, чтобы после перераспределения во всей компоненте нагрузка на каждой вершине была не больше X?

Это возможно тогда и только тогда, когда

sum <= X * size

Почему?

• если каждая из size вершин может иметь не более X, то суммарно компоненте доступно не более X * size;
• если sum > X * size, то разместить всю нагрузку невозможно;
• если sum <= X * size, то нагрузку можно распределить так, чтобы нигде не превысить X.

Именно это условие и проверяется в решении.

Почему достаточно рассматривать только связные компоненты

Связи задают неориентированный граф.

• Внутри одной компоненты каждая вершина достижима из любой другой.
• Значит, нагрузка может «перетекать» по цепочке.
• Между разными компонентами связности передача невозможна.

Следовательно, каждая компонента обрабатывается отдельно, а итоговый ответ должен подходить для всех компонент сразу.

Проверка ответа

Пусть мы хотим проверить, можно ли добиться максимальной нагрузки не больше X.

Тогда для каждой компоненты должны выполняться ограничения:

sum_component <= X * size_component

Если хотя бы для одной компоненты это неверно, то ответ X невозможен.

Если верно для всех — возможен.

Такая проверка работает за O(C), где C — число компонент, если суммы и размеры компонент уже посчитаны.

Почему здесь нужен бинарный поиск

Если значение X подходит, то любое значение больше тоже подходит.

Действительно, если можно уложиться в максимум X, то тем более можно уложиться в X+1, X+2 и так далее.

Значит, функция проверки монотонна:

• маленькие X могут не подходить;
• начиная с некоторого минимального значения — все подходят.

Это классическая ситуация для бинарного поиска по ответу.

Как найти компоненты связности

Для этого удобно использовать DSU (Disjoint Set Union, система непересекающихся множеств).

DSU позволяет:

• быстро объединять вершины ребром,
• быстро узнавать, в какой компоненте находится вершина,

• хранить для каждой компоненты дополнительные данные:

  • размер,
  • сумму нагрузок.

При объединении двух компонент мы просто складываем их размеры и суммы.

Полный алгоритм

1. Считываем N, M.
2. Считываем нагрузки станций.
3. Создаём DSU, где изначально каждая вершина — отдельная компонента.
4. Для каждого ребра u, v объединяем вершины в DSU.
5. Собираем корни всех компонент.

6. Для каждой компоненты знаем:

   • sum — сумму нагрузок,
   • size — размер компоненты.
7. Бинарным поиском ищем минимальное X, для которого для всех компонент выполнено:

sum <= X * size

Разбор на примере

Рассмотрим пример:

N = 3, M = 2
load = [10, 0, 0]
ребра: (1, 2), (2, 3)

Все три вершины находятся в одной компоненте:

• sum = 10
• size = 3

Проверим:

• X = 3: 10 <= 3 * 3 = 9 — нет
• X = 4: 10 <= 4 * 3 = 12 — да

Значит, минимальный ответ равен 4.

Это соответствует распределению 4, 3, 3.

Корректность решения

Лемма 1

Для компоненты размера size и суммарной нагрузки sum значение X достижимо тогда и только тогда, когда sum <= X * size.

Доказательство.

Необходимость очевидна: если в каждой вершине не больше X, то суммарно нельзя разместить больше чем X * size.

Достаточность следует из условия задачи: внутри связной компоненты разрешено перераспределение нагрузки между вершинами. Значит, суммарную нагрузку можно распределить по вершинам компоненты так, чтобы нигде не превысить X, если общей ёмкости X * size хватает. ∎

Лемма 2

Проверка ok(X) монотонна.

Доказательство.

Если sum <= X * size, то тем более sum <= Y * size для любого Y >= X. Значит, если X подходит, то и любое большее значение тоже подходит. ∎

Теорема

Бинарный поиск по X находит минимально возможное значение максимальной нагрузки.

Доказательство.

По лемме 1 проверка ok(X) точно определяет, достижимо ли значение X. По лемме 2 множество подходящих X имеет вид отрезка [ans, +∞). Бинарный поиск по монотонному предикату находит минимальное подходящее значение. ∎

Оценка сложности

DSU

Каждое объединение и поиск работают за почти константное время — O(α(N)), где α — обратная функция Аккермана.

Общая сложность

• построение компонент: O((N + M) * α(N))
• одна проверка: O(C), где C — число компонент, C <= N
• бинарный поиск: O(log S), где S — верхняя граница ответа

Итого:

O((N + M) * α(N) + N * log S)

Для заданных ограничений это решение работает эффективно.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n;
    vector<int> p, r;
    vector<long long> sum;
    vector<int> sz;

    DSU(int n_, const vector<long long>& a) : n(n_), p(n_+1), r(n_+1,0), sum(n_+1,0), sz(n_+1,1) {
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            sum[i] = a[i];
            sz[i] = 1;
        }
    }

    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        sum[a] += sum[b];
        sz[a] += sz[b];
        if (r[a] == r[b]) r[a]++;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<long long> load(N + 1);
    for (int i = 1; i <= N; i++) cin >> load[i];

    DSU dsu(N, load);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    vector<int> roots;
    roots.reserve(N);
    for (int i = 1; i <= N; i++) {
        if (dsu.find(i) == i) roots.push_back(i);
    }

    auto ok = [&](long long X) -> bool {
        for (int r : roots) {
            if (dsu.sum[r] > X * 1LL * dsu.sz[r]) return false;
        }
        return true;
    };

    long long lo = 0, hi = 0;
    for (int r : roots) hi = max(hi, dsu.sum[r]);

    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;
        else lo = mid + 1;
    }

    cout << lo << "\n";
    return 0;
}

Пояснение к реализации на C++

Структура DSU

В DSU хранятся:

• p — родитель вершины,
• r — ранг для эвристики объединения,
• sum — сумма нагрузок в компоненте,
• sz — размер компоненты.

Метод find

Находит корень компоненты с частичным сжатием пути.

Метод unite

Объединяет две компоненты и обновляет:

• суммарную нагрузку,
• размер компоненты.

Список roots

После всех объединений собираются корни всех компонент. Именно по ним потом выполняется проверка ok(X).

Проверка ok(X)

Для каждой компоненты проверяется условие:

if (dsu.sum[r] > X * 1LL * dsu.sz[r]) return false;

Если оно нарушено, значит этого X недостаточно.

Границы бинарного поиска

• lo = 0
• hi = max(sum компоненты)

Почему верхняя граница корректна? Потому что если взять X, равный сумме самой тяжёлой компоненты, то уж точно всю нагрузку этой компоненты можно разместить, не превышая X.

Реализация на Python

import sys
sys.setrecursionlimit(1_000_000)

class DSU:
    __slots__ = ("p", "r", "sz", "sm")

    def __init__(self, n: int, a):
        self.p = list(range(n + 1))
        self.r = [0] * (n + 1)
        self.sz = [1] * (n + 1)
        self.sm = [0] * (n + 1)
        for i in range(1, n + 1):
            self.sm[i] = a[i]

    def find(self, x: int) -> int:
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def unite(self, a: int, b: int) -> None:
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.r[a] < self.r[b]:
            a, b = b, a
        self.p[b] = a
        self.sm[a] += self.sm[b]
        self.sz[a] += self.sz[b]
        if self.r[a] == self.r[b]:
            self.r[a] += 1


def main() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)

    n = int(next(it))
    m = int(next(it))

    load = [0] * (n + 1)
    for i in range(1, n + 1):
        load[i] = int(next(it))

    dsu = DSU(n, load)

    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        dsu.unite(u, v)

    roots = []
    for i in range(1, n + 1):
        if dsu.find(i) == i:
            roots.append(i)

    def ok(x: int) -> bool:
        for r in roots:
            if dsu.sm[r] > x * dsu.sz[r]:
                return False
        return True

    lo = 0
    hi = 0
    for r in roots:
        if dsu.sm[r] > hi:
            hi = dsu.sm[r]

    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1

    sys.stdout.write(str(lo))


if __name__ == "__main__":
    main()

Пояснение к реализации на Python

По сути это тот же алгоритм, что и в C++:

• DSU хранит компоненты;
• в каждой компоненте поддерживаются сумма sm и размер sz;
• после построения всех компонент выполняется бинарный поиск по ответу.

Особенности реализации:

• используется sys.stdin.buffer.read() для быстрого ввода;
• __slots__ немного уменьшает накладные расходы на объект DSU;
• все вычисления корректно работают с большими числами, так как в Python целые числа длинные.

Типичные ошибки

1. Искать максимум внутри компоненты, а не среднюю ёмкость

Иногда кажется, что ответ для компоненты связан с её текущей максимальной нагрузкой. Это неверно: после перераспределения важно только, хватает ли суммарной ёмкости X * size.

2. Пытаться моделировать само перераспределение

Это не нужно. Достаточно понять критерий существования ответа, а не строить конкретное распределение.

3. Забыть про большие числа

Так как load[i] могут быть до 10^9, а вершин много, суммы нужно хранить в long long в C++.

4. Проверять вершины, а не компоненты

Ограничение формулируется на уровне компонент. Проверять каждую вершину отдельно после объединений бессмысленно.

Итог

Задача решается через сочетание двух идей:

• DSU для нахождения компонент связности и подсчёта их параметров;
• бинарный поиск по ответу для нахождения минимально возможного максимума.

Главная формула решения:

sum_component <= X * size_component

Если она выполнена для всех компонент, то значение X достижимо.

Минимальное такое X и есть ответ.