Custom Min Spanning Tree
1.0.0
Construir un árbol de expansión a partir de datos de entrada debe obedecer estas tres reglas básicas:
Imagen 1. Esquemas de posibles conexiones entre nodos gráficos. Las posibles conexiones se representan como bordes. Las conexiones que pueden formar el árbol de expansión deseado se resaltan en rojo. Los casos a), b), c) corresponden a los ejemplos 1, 2, 3 a continuación. En algunos casos (p. Ej. En los casos B y C), más de un árbol de expansión puede satisfacer las demandas del problema. Sin embargo, todos esos árboles de expansión comparten la misma longitud total. El caso a) ilustra la importancia de la Regla 3. Existe los árboles que abarcan los bordes (1, 5) y (5, 4) que satisfacen la Regla 2 pero no satisfacen la Regla 3, ya que la longitud total de ninguno de ellos es al menos 17.
Se da la lista de todas las conexiones posibles entre los nodos y las longitudes de conexión respectivas. Calcule la longitud total de un árbol de expansión que satisface las tres reglas presentadas en la descripción.
Los conjuntos de datos para la tarea fueron creados por maestros de la Universidad Técnica Checa para la "algoritmización avanzada".
La primera línea de la entrada consta de dos enteros N y M separados por el espacio. El valor n es el número de nodos. El valor M es el número de posibles conexiones entre pares de nodos. A continuación, hay m líneas, donde cada línea representa una posible conexión. La línea contiene tres enteros D1, D2, L separados por el espacio, lo que significa que la longitud de la posible conexión entre los nodos D1 y D2 es igual a L. Los detectores están numerados de 1 a N. Las conexiones posibles se enumeran en un orden aleatorio. Sostiene N ≤ 30000 y M ≤ 300000. Cada longitud es como máximo 10^9.
La salida es una línea que contiene la longitud total mínima de la red requerida. El resultado no es mayor que 2^60.
Los datos de entrada del ejemplo 1 y la red resultante se representan en la imagen 1 a).
Los datos de entrada del ejemplo 2 y la red resultante se representan en la imagen 1 b).
Los datos de entrada del ejemplo 2 y la red resultante se representan en la imagen 1 c).
La tarea se implementa en Java utilizando el algoritmo optimizado de la sindicato (explicado aquí). En el algoritmo se utiliza una versión modificada de HashMap implementada por los autores Justin Couch, Alex Chaffee y Stephen Colebourne. Este hashmap usa solo enteros primitivos y no objetos enteros Java, lo que resultó en un rendimiento mejorado.
