Планирование сети
В нефтяной розничной индустрии расположение автозаправочных станций играет ключевую роль в увеличении прибыли компании. Чтобы максимизировать доход, компания применяет стратегию "Планирование сети" для выбора мест, где следует строить новые автозаправочные станции.
Вы выступаете в роли консультанта для этой компании. Вам предоставлены данные, включающие количество городов и их связи, спрос на топливо в литрах, список городов с уже существующими автозаправочными станциями и общее количество новых станций, которые планируется построить в этом году.
Ваша задача — определить, в каких городах следует строить новые автозаправочные станции, чтобы максимизировать прибыль. Задача кажется простой, не так ли?
Вот что вам нужно знать:
В стране N городов. В каждом городе может быть только одна автозаправочная станция.
Каждая автозаправочная станция способна удовлетворить неограниченный спрос на топливо.
Станция удовлетворяет 70% спроса на топливо в своем городе и 10% спроса каждого соседнего города, независимо от наличия у них собственных станций.
Например, если Город A, Город B и Город C связаны, и у Города A и Города B есть станции, то Город A удовлетворяет 70% своего спроса плюс 10% от спроса Города B и 10% от Города C. Аналогично для Города B.
Из-за географических ограничений у каждого города не более трех соседей.
Общий доход компании прямо пропорционален общему удовлетворенному спросу на топливо.
Входные данные
Первая строка ввода — количество тестовых случаев T ≤ 10.
Каждый тестовый случай начинается с числа городов N (1 ≤ N ≤ 100000).
Следующие N строк содержат целое число D_i (0 ≤ D_i ≤ 1000) — спрос на топливо в каждом городе.
Следующая строка содержит целое число E — количество связей.
Следующие E строк содержат 2 целых числа C_1 и C_2, описывающих двунаправленные соседние города. Входные данные не содержат дублирующихся связей (т.е. если есть связь для (C_1, C_2), то не будет связи для (C_2, C_1) в том же наборе данных). Все города пронумерованы от 1 до N.
Следующая строка содержит целое число S (0 ≤ S < N) — количество существующих автозаправочных станций.
Следующие S строк содержат целое число C — город с уже существующей станцией.
Последняя строка содержит целое число M (1 ≤ M ≤ N–S) — точное количество новых станций, которые нужно построить в этом году.
Вывод
Для каждого тестового случая выведите две строки.
Первая строка — положительное целое число (округленное по общим правилам) — максимальный общий спрос на топливо, который можно удовлетворить, включая существующие и новые станции в оптимальных городах.
Вторая строка — список городов, где следует построить новые станции, разделенных пробелами и в порядке возрастания. Города с существующими станциями не включаются в этот список. Если существует несколько решений, выберите то, которое идет первым в лексикографическом порядке.
Иллюстрация для этого примера
Первый пример
Если построить новую станцию только в Городе 3, это максимизирует общий объем поставок до 360 литров.
Второй пример
Есть два оптимальных решения. Строительство новых станций в городе 1, городе 2 и городе 5 даст такую же прибыль, как и в городе 1, городе 3 и городе 5. Ответ должен быть 1 2 5, так как это решение идет первым в лексикографическом порядке. Общий объем поставок составит 268.2 для города 1, 182.6 для города 2 и 290 для города 5. Город 4, с уже существующей станцией, поставляет 150 литров. Общий объем поставок составляет 268.2 + 182.6 + 290 + 150 = 890.8, что округляется до 891.
