Custom Min Spanning Tree

Пользовательское минимальное охраняющее дерево

Описание

Создание живого дерева из входных данных должно подчиняться этим трем основным правилам:

1. График должен быть деревом и содержать все узлы.
2. График должен содержать максимально возможное количество краев определенной длины, независимо от стоимости, связанных с этими краями.
3. Общая сумма длины края полученного графика, касающегося первого и второго правила, должна быть сведена к минимуму.

Изображение 1. Схемы возможных соединений между узлами графика. Возможные соединения изображены как края. Соединения, которые могут сформировать желаемое охраняющее дерево, выделены красным. Случаи a), b), c) соответствуют примерам 1, 2, 3 ниже. В некоторых случаях (например, в случаях B и C) более одного дерева охватывающего дерева может удовлетворить требования проблемы. Однако все такие охватывающие деревья имеют одинаковую общую длину. Случай а) иллюстрирует важность правила 3. Существуют охватывающие деревья, содержащие края (1, 5) и (5, 4), которые удовлетворяют правилу 2, но не удовлетворяют правилу 3, поскольку общая длина любого из них составляет не менее 17.

Задача

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

Наборы данных для этой задачи были созданы учителями Чешского технического университета для предметной «передовой алгоритмизации».

Вход

Первая линия ввода состоит из двух целых чисел N и M, разделенных пространством. Значение n - количество узлов. Значение M - это количество возможных соединений между парами узлов. Далее, есть M Lines, где каждая строка представляет одно возможное соединение. Линия содержит три целых числа D1, D2, L, разделенные пространством, что означает, что длина возможного соединения между узлами D1 и D2 равна L. Детекторы пронумерованы от 1 до N. Возможные соединения перечислены в случайном порядке. Он содержит N ≤ 30000 и M ≤ 300000. Каждая длина составляет не более 10^9.

Выход

Выход - это одна линия, содержащая минимальную общую длину необходимой сети. Результат не больше 2^60.

Пример 1

Пример 1 входные данные и полученная сеть изображены на изображении 1 а).

Пример 2

Пример 2 Входные данные и полученная сеть изображены на изображении 1 B).

Пример 3

Пример 2 входные данные и полученная сеть изображены на изображении 1 C).

Решение

Задача реализована в Java с использованием оптимизированного алгоритма инакомых союдов (объясняется здесь). В алгоритме используется модифицированная версия HashMap, реализованную авторами Джастином Кушем, Алексом Чаффи и Стивеном Колебурном. Этот HashMap использует только примитивные целые числа, а не Java Integer объектов, что привело к повышению производительности.