Несвязное множество

Задача 1. Несвязное множество

Пусть задан некоторый неориентированный вершинно-взвешенный граф , состоящий из вершин и ребер, при этом каждая вершина характеризуется натуральным числом из множества , соответствующим «ценности» вершины.
Смежными называются вершины, имеющие общее ребро.
Несвязным множеством вершин называется такое подмножество вершин , что никакие две вершины из этого множества не являются смежными.
Ценностью множества вершин называется сумма ценностей всех вершин, входящих в это множество.

Задача

Ваша задача – выбрать из заданного графа несвязное множество вершин таким образом, чтобы ценность данного множества была как можно больше.

Технический регламент

Все участники получают три файла task1.txt, task2.txt и task3.txt, каждый из которых содержит описание одного графа в следующем формате.
<Число вершин>
<Ценность первой вершины> <Ценность второй вершины> … <Ценность последней вершины>
<Число ребер>
<Первая вершина первого ребра> <Вторая вершина первого ребра>
<Первая вершина второго ребра> <Вторая вершина второго ребра>
<Первая вершина третьего ребра> <Вторая вершина третьего ребра>
…
<Первая вершина последнего ребра> <Вторая вершина последнего ребра>
После окончания соревнования необходимо сдать на проверку три файла ans1.txt, ans2.txt и ans3.txt, каждый из которых должен содержать ответ участника на соответствующую задачу в следующем формате.
<Число выбранных вершин>
<Номер первой выбранной вершины> <Номер второй выбранной вершины> … <Номер последней выбранной вершины>
Обратите внимание на тот факт, что вершины нумеруются с единицы
Для уточнения деталей обратитесь к примеру.
В процессе решения участники могут пользоваться любыми источниками информации, однако в целях обеспечения равной борьбы рекомендуется воздерживаться от поиска методов решения предлагаемой задачи в Интернете и коллективного обсуждения.

Система оценки

Итоговый балл участника рассчитывается как , где , и – мощность предлагаемого в качестве ответа подмножества в каждой из трех задач. В случае, когда подмножество не существует или не удовлетворяет условию задачи, соответствующая мощность принимается равной нулю. Победителем считается участник, набравший максимальный балл.

Пример

task1.txt
ans1.txt
5
10 6 6 1 1
4
1 2
3 1
3 5
1 4
2
1 5


Предлагаемый ответ будет оценен в 11 баллов, к итоговой сумме будет прибавлено 22 балла.

0