Разлом сети

Исследовательская сеть состоит из n узлов и m двусторонних связей. Для аварийного эксперимента узлы нужно разделить на две лаборатории. Связь полезна, если её концы оказались в разных лабораториях; связь внутри одной лаборатории создаёт помехи.

Для каждой связи задан положительный вес. Требуется найти разбиение, минимизирующее суммарный вес связей, оба конца которых находятся в одной группе.

Это оптимизационная задача: от вас не требуется находить доказанно оптимальный ответ. Любое корректное разбиение получает результат, а более низкое значение целевой функции лучше.

Входные данные

В первой строке находятся два целых числа n и m — количество узлов и связей.

В следующих m строках записаны три целых числа u, v, w: связь соединяет различные вершины u и v, её вес равен w.

• 1 <= n <= 12000;
• 1 <= m <= 260000;
• 1 <= w <= 1000000;
• кратных рёбер и петель нет.

Выходные данные

Выведите ровно n целых чисел 0 или 1. Число с номером i задаёт группу вершины i.

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

Целевая функция

Пусть c[i] — выведенная группа вершины i. Проверяющая программа вычисляет

S = sum(w(u,v) для всех рёбер, у которых c[u] = c[v]).

Нужно минимизировать S. Эквивалентно можно максимизировать вес разреза — сумму весов рёбер между разными группами.

Баллы за каждый скрытый тест вычисляются платформой относительно результата готовой базовой эвристики B и лучшего известного результата R:

q = clamp((B - S) / (B - R), 0, 1).

Итоговые баллы — взвешенная сумма по десяти тестам. Во время тура R может улучшаться вместе с лучшими результатами участников.

Пример

Ввод

5 6
1 2 4
1 3 2
2 3 3
2 4 5
3 5 6
4 5 1

Вывод

0 1 1 0 0

В этом разбиении связи (2,3) и (4,5) остались внутри групп. Поэтому значение целевой функции равно 3 + 1 = 4. Остальные четыре связи пересекают разрез и штрафа не дают.

Что важно учесть

Скрытые графы велики, а их структуры различаются. Среди них есть разреженные и плотные графы, сообщества, почти двудольные графы с шумом, геометрически локальные связи, тяжёлые хабы, решётки с дальними связями и смесь нескольких режимов. Решение, подогнанное под одну структуру, не будет устойчивым на остальных.

Полезные направления для экспериментов:

1. Жадно назначать вершины по убыванию взвешенной степени, выбирая менее штрафную сторону.
2. Улучшать готовое разбиение переворотами одной вершины, быстро поддерживая выигрыш каждого переворота.
3. Использовать много стартов, случайные возмущения, tabu search, simulated annealing или пакетные перестановки нескольких вершин.
4. Выделять тяжёлые рёбра, хабы и сообщества и по-разному настраивать поиск для плотных и разреженных частей.

Полный перебор требует порядка 2^(n-1) разбиений. Лимит рассчитан так, чтобы точное решение скрытых тестов было практически недостижимо; соревноваться нужно качеством приближения.