Агентурная сеть
(Время: 0,25 сек. Память: 32 Мб Сложность: 73%)
Близится день окончания войны. Поэтому агентурную сеть необходимо уменьшить. Агентурная сеть описывается графом контактов. Ежедневно выбирают одного куратора для «перекрытия каналов». Все агенты-одиночки, у которых единственный контакт – этот куратор, выводятся из сети и переводятся под прямое управление куратора (они больше не считаются агентами-одиночками). У каждого куратора есть риск операции R.
Нужно найти минимально возможное число агентов после завершения операций, минимальный суммарный риск и количество способов для достижения этого минимума. Два способа считаются различными, если на i-й день выбранный куратор отличается или количество дней, необходимых для завершения операций. Так как количество способов завершения операций может быть довольно большим, выведите результат по модулю 109 + 7.
Гарантируется, что между любыми двумя агентами будет не более одного прямого соединения. Кроме того, каждая пара агентов будет напрямую или косвенно связана.
Входные данные
Входной файл INPUT.TXT в первой строке содержит два натуральных числа N и M – количество агентов и связей между ними (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10000).
Следующая строка содержит N натуральных чисел Ri (1 ≤ Ri ≤ 1000), представляющих риск операции i-го агента. Следующие M строк по два натуральных числа ai и bi - номера связанных агентов (1 ≤ ai, bi ≤ N; ai ≠ bi).
Выходные данные
В выходной файл OUTPUT.TXT выведите три числа через пробел – минимально возможное число агентов после завершения операций, минимальный суммарный риск и количество способов для достижения этого минимума.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 12 12
1 5 4 6 9 7 1 2 1 4 9 3
3 4
3 1
2 3
6 5
7 10
3 7
5 4
12 10
10 9
5 7
6 8
10 11 | 4 25 30 |
Пояснение к примеру
В конце концов осталось 4 агента, минимальный суммарный риск равен 4 + 4 + 7 + 9 + 1 = 25. 30 способов «перекрытия каналов» через нумерацию вершин получается перестановками чисел {3, 10, 6, 5, 7}, где 7 идёт после 10 и 5 идёт после 6.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
