Custom Min Spanning Tree

Benutzerdefinierte minimale Spannungsbaum

Beschreibung

Der Aufbau eines Spannungsbaums aus Eingabedaten sollte diesen drei Grundregeln befolgen:

1. Die Grafik muss ein Baum sein und alle Knoten enthalten.
2. Die Grafik sollte eine maximal mögliche Anzahl von Kanten mit einer bestimmten Länge enthalten, unabhängig von den mit diesen Kanten verbundenen Kosten.
3. Die Gesamtsumme der Kantenlängen der daraus resultierenden Grafik in Bezug auf die erste und die zweite Regel sollte minimiert werden.

Bild 1. Schemata möglicher Verbindungen zwischen Grafikknoten. Mögliche Verbindungen werden als Kanten dargestellt. Die Verbindungen, die den gewünschten Spanning -Baum bilden können, werden rot hervorgehoben. Die Fälle a), b), c) entsprechen den Beispielen 1, 2, 3 unten. In einigen Fällen (z. B. in Fällen B und C) können mehr als ein Spannungsbaum die Problemanforderungen erfüllen. Alle dieser Spannbäume haben jedoch die gleiche Gesamtlänge. Der Fall a) zeigt die Bedeutung von Regel 3. Es gibt Spannungsbäume mit Kanten (1, 5) und (5, 4), die Regel 2 erfüllen, aber Regel 3 nicht als die Gesamtlänge einer von ihnen erfüllen mindestens 17.

Aufgabe

Die Liste aller möglichen Verbindungen zwischen den Knoten und den jeweiligen Verbindungslängen wird angegeben. Berechnen Sie die Gesamtlänge eines Spannungsbaums, der alle drei in Beschreibung dargestellten Regeln erfüllt.

Die Datensätze für die Aufgabe wurden von Lehrern der tschechischen technischen Universität für das Thema „Erweiterte Algorithmisierung“ erstellt.

Eingang

Die erste Zeile der Eingabe besteht aus zwei Zahlen N und M, die durch den Raum getrennt sind. Wert n ist die Anzahl der Knoten. Wert M ist die Anzahl der möglichen Verbindungen zwischen Knotenpaaren. Als nächstes gibt es M -Zeilen, in denen jede Zeile eine mögliche Verbindung darstellt. Die Linie enthält drei Zahlen D1, D2, L durch den Raum getrennt, was bedeutet, dass die Länge der möglichen Verbindung zwischen Knoten D1 und D2 gleich L entspricht. Es hält n ≤ 30000 und m ≤ 300000. Jede Länge beträgt höchstens 10^9.

Ausgabe

Die Ausgabe ist eine Zeile, die die minimale Gesamtlänge des erforderlichen Netzwerks enthält. Das Ergebnis ist nicht größer als 2^60.

Beispiel 1

Beispiel 1 Eingabedaten und das resultierende Netzwerk sind in Bild 1 a) dargestellt.

Beispiel 2

Beispiel 2 Eingabedaten und das resultierende Netzwerk sind in Bild 1 b dargestellt).

Beispiel 3

Beispiel 2 Eingabedaten und das resultierende Netzwerk sind in Bild 1 C dargestellt).

Lösung

Die Aufgabe wird in Java unter Verwendung eines optimierten Union-Find-Algorithmus (hier erklärt) implementiert. Im Algorithmus wird eine modifizierte Version von HashMap verwendet, die von den Autoren Justin Couch, Alex Chaffee und Stephen Colebourne implementiert wurde. Dieser HashMap verwendet nur primitive ganze Zahlen und nicht Java -Integer -Objekte, was zu einer verbesserten Leistung führte.