Как решить NP-полную задачу на сортировку предметов по голосам?
Помогите решить задачу с помощью приближенного алгоритма.
Задача: есть набор из n предметов, и есть m голосов, например 1 3 1, что говорит о том, что предмет 1 лучше предмета 3, нужно найти такой порядок предметов, который бы учитывал как максимум в два раза меньше голосов от максимально возможного.
sim3x,
Формат входного файла
В первой строке записано число n произведений искусства и число m голосов (1 ≤ n, m ≤ 300 000). Все произведения искусства занумерованы числами от 1 до n.
В каждой из следующих m строк записана тройка чисел x, y и z (1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 2), соответствующих одному голосу, где x и y — номера сравниваемых произведений, а z равно 1, если произведение x понравилось пользователю больше, чем y, или 2 в противном случае.
Формат выходного файла
В первой строке выведите число голосов, которые будут учтены в предложенном порядке. Во второй строке выведите перестановку чисел от 1 до n — порядок, при котором не меньше половины от максимально возможного числа голосов отдаёт предпочтение произведению, идущему в этом порядке раньше.
asifilatova, условие некорректно при n>3, поскольку между 1 и 3 позициями в перестановке предпочтение должно отдать не меньше максимально возможного числа голосов, т.е. все голоса должны быть (1 2 х) и (1 3 х).
