Как решить NP-полную задачу на сортировку предметов по голосам?

Question

[asifilatova]

Помогите решить задачу с помощью приближенного алгоритма.
Задача: есть набор из n предметов, и есть m голосов, например 1 3 1, что говорит о том, что предмет 1 лучше предмета 3, нужно найти такой порядок предметов, который бы учитывал как максимум в два раза меньше голосов от максимально возможного.

Comments

[sim3x]

Дайте больше примеров

[asifilatova]

sim3x,
3 3
1 2 1
2 3 1
3 1 1

Output:
1
3 2 1

Здесь учитывается 1 голос, а можно 2: 1 2 3

[sim3x]

asifilatova, опишите саму матрицу и вывод

[xmoonlight]

asifilatova, а почему не 1 3 2 (при одном голосе)?

[asifilatova]

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 — порядок, при котором не меньше половины от максимально возможного числа голосов отдаёт предпочтение произведению, идущему в этом порядке раньше.

[chupasaurus]

asifilatova, условие некорректно при n>3, поскольку между 1 и 3 позициями в перестановке предпочтение должно отдать не меньше максимально возможного числа голосов, т.е. все голоса должны быть (1 2 х) и (1 3 х).

[xmoonlight]

asifilatova, ощущение, что нужна формула попарного сравнения каждого с каждым. Это так?