Custom Min Spanning Tree
1.0.0
La construction d'un arbre couvrant à partir des données d'entrée devrait obéir à ces trois règles de base:
Image 1. Schémas de connexions possibles entre les nœuds graphiques. Les connexions possibles sont représentées comme des bords. Les connexions qui peuvent former l'arbre couvrant souhaité sont mises en évidence en rouge. Les cas a), b), c) correspondent aux exemples 1, 2, 3 ci-dessous. Dans certains cas (par exemple dans les cas B et C), plus d'un arbre couvrant peut satisfaire aux demandes du problème. Cependant, tous ces arbres couvrant partagent la même longueur totale. Le cas a) illustre l'importance de la règle 3. Il existe des arbres couvrant les arbres contenant des bords (1, 5) et (5, 4) qui satisfont la règle 2 mais ne satisfont pas à la règle 3 car la durée totale de l'une d'entre elles est d'au moins 17.
La liste de toutes les connexions possibles entre les nœuds et les longueurs de connexion respectives est donnée. Calculez la longueur totale d'un arbre couvrant qui satisfait les trois règles présentées dans la description.
Les ensembles de données pour la tâche ont été créés par les enseignants de l'Université technique tchèque pour «l'algorithmisation avancée».
La première ligne de l'entrée se compose de deux entiers N et M séparés par l'espace. La valeur n est le nombre de nœuds. La valeur m est le nombre de connexions possibles entre les paires de nœuds. Ensuite, il y a des lignes M, où chaque ligne représente une connexion possible. La ligne contient trois entiers D1, D2, L séparés par l'espace, ce qui signifie que la longueur de la connexion possible entre les nœuds D1 et D2 est égale à L. Les détecteurs sont numérotés de 1 à N. Les connexions possibles sont répertoriées dans un ordre aléatoire. Il contient n ≤ 30000 et m ≤ 300000. Chaque longueur est au plus 10 ^ 9.
La sortie est une ligne contenant la longueur totale minimale du réseau requis. Le résultat n'est pas supérieur à 2 ^ 60.
Exemple 1 Les données d'entrée et le réseau résultant sont représentés dans l'image 1 a).
Exemple 2 Les données d'entrée et le réseau résultant sont représentés dans l'image 1 b).
Exemple 2 Les données d'entrée et le réseau résultant sont représentés dans l'image 1 C).
La tâche est mise en œuvre en Java en utilisant un algorithme de recherche d'union optimisé (expliqué ici). Dans l'algorithme, il est utilisé une version modifiée de Hashmap implémentée par les auteurs Justin Couch, Alex Chaffee et Stephen Colebourne. Ce hashmap utilise uniquement des entiers primitifs et non des objets entiers Java, ce qui a entraîné une amélioration des performances.
