На их форуме наконец-то появилась тема-шаблон для разбора — думаю, скоро там опишут различные возможные решения.

У меня все было довольно просто. Забиваем на маленькие графы, потому что они дают мало штрафа. Забиваем на разреженные графы, потому что они дают мало штрафа. Можно написать туда отдельные решения, но на это еще нужно потратить время) Поэтому я решал только для насыщенных графов, к которым, фактически, вся задача и сводилась (с учетом особенностей начисления очков).

Напишем что-то вроде поиска мин.остова. Будем добавлять в ответ "самую выгодную" вершину, по одной на итерации, пока не получим N/2 вершин. Почти всегда (у меня — N/2-N/9 итераций) будем использовать такую оценку — нужно добавить в ответ ту вершину, для которой общая стоимость ребер между ней и вершинами из ответа максимальна. Т.е. мы пытаемся жадно избавиться от плохих вершин.

На последних итерациях будем использовать другую функцию — берем в ответ ту вершину, добавление которой в ответ максимально улучшит наше пенальти (т.е. теперь нас интересует разность между весами ребер из этой вершины в ответ и из этой вершины за пределы ответа).

На контесте это набрало 0.936, 5 место.