Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Умные энергосистемы Уровень: Профи

📜 Четвертая технология

Ты исследуешь заброшенную энергетическую станцию далёкого техногенного прошлого.

Система всё ещё жива: датчики мигают, распределительные щиты гудят, а древний управляющий модуль пытается удержать сеть в стабильном состоянии.

Из архивных логов ты узнаёшь главное правило этой станции:

Перегрузка одного узла может обрушить всю систему.

Сеть умеет перераспределять энергию между секциями — но строго по заданным каналам и с определёнными ограничениями. Твоя задача — восстановить баланс и добиться максимально устойчивого режима работы.

🧠 Немного о технологии

Современные энергосистемы — это не просто провода и генераторы. Это сложные киберфизические комплексы, которые:

• непрерывно измеряют состояние сети,
• прогнозируют нагрузку,
• управляют потоками мощности,
• реагируют на перегрузки в реальном времени.

Такие сети называют умными энергосистемами (Smart Grid).

Почему проблема пиков критична

Пиковая нагрузка — главный враг энергетической инфраструктуры. Когда отдельный элемент сети перегружен, возникают:

• перегрев кабелей и трансформаторов,
• ускоренное старение оборудования,
• рост потерь энергии,
• просадки напряжения,
• риск аварийного отключения.

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

Поэтому энергетика стремится к ключевой цели:

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

📌 Распределение в энергосистемах

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

Объекты системы

• Станции (узлы) — подстанции, секции шин, распределительные пункты.
• Нагрузка — мощность, проходящая через узел в текущий момент.
• Связи передачи — линии электропередачи, трансформаторы, межсекционные перемычки.

Что означает перераспределение энергии

Это не перенос «куска энергии», а изменение того, как формируются потоки мощности:

• переключение части потребителей на другой источник питания,
• изменение конфигурации сети,
• подпитка района через резервную линию,
• использование накопителей энергии,
• временное снижение потребления управляемой нагрузкой.

Инженерные ограничения

Любое перераспределение должно учитывать:

• пропускную способность линий и трансформаторов,
• допустимые токи и тепловые лимиты,
• допустимые диапазоны напряжения,
• технические ограничения коммутаций,
• требования надёжности (устойчивость при отказе элемента).

Сеть не может перераспределять мощность произвольно — каждое действие подчинено физике и регламентам.

📌 Задача

Даны нагрузки станций и правила передачи энергии.

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

📥 Формат входных данных

Первая строка: N M — количество станций и количество допустимых связей.

Вторая строка: load1 load2 ... loadN — исходные нагрузки станций.

Следующие M строк: u v — разрешена передача энергии между станциями u и v.

Ограничения

• 1 ≤ N ≤ 2·10^5
• 0 ≤ load[i] ≤ 10^9
• 1 ≤ M ≤ 2·10^5

📤 Формат выходных данных

Выведите одно число — минимально возможную максимальную нагрузку.

📘 Примеры

Пример 1

Входные данные:

3 2
10 0 0
1 2
2 3

Выходные данные:

4

Пояснение: нагрузку 10 можно перераспределить по цепочке между тремя станциями. Наиболее равномерное распределение: 4, 3, 3. Максимум равен 4.

Пример 2

Входные данные:

4 1
8 1 1 1
1 2

Выходные данные:

5

Пояснение: станция 1 связана только со станцией 2. Часть нагрузки можно передать, но станции 3 и 4 изолированы. Минимальный возможный максимум — 5.

Пример 3

Входные данные:

5 0
5 2 7 1 4

Выходные данные:

7

Пояснение: связей нет, перераспределение невозможно. Ответ равен исходному максимальному значению — 7.