Планування мережі#6572

Планування мережі

1 секунда

64 мегабайти

Легка

У нафтовій індустрії розташування автозаправних станцій є критично важливим для прибутковості компанії. Щоб максимізувати прибуток, компанія використовує концепцію "Планування мережі" для вибору місць будівництва нових автозаправних станцій.

Ви виступаєте консультантом для цієї компанії. Вам надано дані, що включають кількість міст та їхні зв'язки, обсяг попиту на паливо в літрах, список міст з уже існуючими автозаправними станціями, а також загальну кількість нових станцій, які планується побудувати цього року.

Компанія очікує від вас відповідь на питання: "В яких містах слід побудувати нові автозаправні станції, щоб максимізувати прибуток?" Звучить просто, чи не так?

Ось кілька важливих деталей, які вам знадобляться:

У цій країні є $N$ міст. Кожне місто може мати лише одну автозаправну станцію.
Вважається, що кожна автозаправна станція може задовольнити необмежений попит на паливо.
Кожна автозаправна станція забезпечує $70%$ попиту на паливо (в літрах) у своєму місті, плюс $10%$ попиту кожного сусіднього міста, незалежно від того, чи мають сусідні міста власну автозаправну станцію.
Наприклад, якщо Місто A, Місто B та Місто C всі з'єднані; Місто A та Місто B мають свої автозаправні станції, тоді Місто A забезпечить $70%$ попиту на паливо для себе плюс $10%$ від Міста B та $10%$ від Міста C. Те ж саме стосується Міста B.
Через географічні обмеження кожне місто має не більше трьох сусідніх міст.
І останнє, але не менш важливе: загальний дохід компанії прямо пропорційний загальному попиту на паливо, який вони можуть задовольнити.

Вхідні дані

Перша строка вводу - це кількість тестових випадків $T \leq 10$ T \le 10.

Кожен тестовий випадок починається з кількості міст $N$ ( $1 \leq N \leq 100000$ 1 \le N \le 100000).

Наступні $N$ рядків містять ціле число $D_{i}$ D_i ( $0 \leq D_{i} \leq 1000$ 0 \le D_i \le 1000) - попит на паливо в кожному місті.

Наступний рядок містить ціле число $E$ - кількість зв'язків.

Наступні $E$ рядків містять $2$ цілі числа $C_{1}$ C_1 та $C_{2}$ C_2, що описують двосторонні сусідні міста. У вхідних даних не буде повторюваних зв'язків (тобто, якщо є зв'язок для $(C_{1}, C_{2})$ (C_1, C_2), не буде зв'язку для $(C_{2}, C_{1})$ (C_2, C_1) в тому ж наборі даних). Також зауважте, що всі міста нумеруються від $1$ до $N$ .

Наступний рядок містить ціле число $S$ ( $0 \leq S < N$ 0 \le S < N) - кількість існуючих автозаправних станцій.

Наступні $S$ рядків містять ціле число $C$ - місто, яке вже має автозаправну станцію.

Останній рядок містить ціле число $M$ ( $1 \leq M \leq N - S$ 1 \le M \le 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$ 268.2 + 182.6 + 290 + 150 = 890.8. Це округлюється до $891$ .

Приклади

Приклад 1