Лучшая звезда со спицами

Средняя

Дан неориентированный граф из n вершин с номерами от 0 до n - 1. У вершины i есть ценность values[i] (может быть отрицательной). Список links содержит рёбра: links[j] = [a, b] соединяет вершины a и b. **Звезда** — это вершина-центр вместе с любым набором её соседей (возможно, пустым); рёбра от центра к выбранным соседям называются спицами. Ценность звезды — сумма ценностей центра и всех выбранных соседей. Верните наибольшую ценность звезды, в которой не больше max_spokes спиц.

Пример 1

values=[4, -1, 7, 3, 2], links=[[0, 1], [0, 2], [0, 3], [3, 4]], max_spokes=2 → 14

Центр 0 (значение 4) соединён с 1, 2 и 3. Берём две лучшие спицы — 7 и 3: 4 + 7 + 3 = 14.

Пример 2

values=[-6, -2, -9], links=[[0, 1], [1, 2]], max_spokes=2 → -2

Все значения отрицательны, поэтому выгоднее не брать ни одной спицы и выбрать центр 1 со значением −2.

Пример 3

values=[5, 8], links=[], max_spokes=1 → 8

Рёбер нет, звезда — это одна вершина; лучшая из них — 8.

Ограничения

1 ≤ n = len(values) ≤ 10⁵
-10⁴ ≤ values[i] ≤ 10⁴
0 ≤ len(links) ≤ min(n·(n − 1)/2, 10⁵)
0 ≤ a, b ≤ n − 1, a ≠ b
Каждая пара вершин соединена не более чем одним ребром
0 ≤ max_spokes ≤ n − 1

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy Graph Array Sorting Heap (Priority Queue)

Вход

values=[4, -1, 7, 3, 2], links=[[0, 1], [0, 2], [0, 3], [3, 4]], max_spokes=2

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 104 теста на сервере, включая скрытые.