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

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

Смежными называются вершины, имеющие общее ребро.

Несвязным множеством вершин называется такое подмножество вершин , что никакие две вершины из этого множества не являются смежными.

Ценностью множества вершин называется сумма ценностей всех вершин, входящих в это множество.

Задача

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

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

Все участники получают три файла 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 балла.

---

Смотрите также файлы

• МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ.docx

• Отчет по практике.doc

• Этика.doc

• ДИПЛОМНА РОБОТА.docx

• на проверку курсач Лисовская 972.docx