Graph Algorithmus Lösung richtig gemacht?
Ich bin auf ein Problem mit dem letzten Facebook Hacker Cup gestoßen (das sind NICHT meine Hausaufgaben, ich finde es nur sehr interessant) und ich dachte auch an eine seltsame, aber ziemlich gute Lösung. Könntest du bitte meinen Gedanken überprüfen? Hier ist die Aufgabe:
Sie erhalten ein Netzwerk mit N Städten und M bidirektionalen Straßen verbinden diese Städte. Die ersten K Städte sind wichtig. Sie müssen das Minimum entfernen Anzahl der Straßen so, dass im restlichen Netzwerk keine Zyklen vorhanden sind enthalten wichtige Städte. Ein Zyklus ist eine Folge von mindestens drei verschiedenen Städte, so dass jedes Paar benachbarter Städte durch eine Straße verbunden sind und die erste und die letzte Stadt in der Folge sind ebenfalls durch eine Straße verbunden.
Eingabe
Die erste Zeile enthält die Anzahl der Testfälle T.Jeder Fall beginnt mit einer Zeile, die ganze Zahlen N, M und K enthält, die darstellen die Anzahl der Städte, die Anzahl der Straßen und die Anzahl der wichtigen Städte, beziehungsweise. Die Städte sind von 0 bis N-1 nummeriert, und die wichtigen Städte sind von 0 bis K-1 nummeriert. Die folgenden M Zeilen enthalten zwei ganze Zahlen a [i] und b [i], 0 ≤ i & lt; M, das sind zwei verschiedene Städte, die durch eine Straße verbunden sind.
Es ist garantiert, dass 0 ≤ a [i], b [i] & lt; N und a [i] ≠ b [i]. Es wird um die meiste Straße zwischen zwei Städten.
Ausgabe
Für jeden der Testfälle, die in der Reihenfolge von 1 bis T nummeriert sind, Ausgabe "Case #i:" gefolgt von einer einzigen ganzen Zahl, der Mindestanzahl von Straßen, die es sein muss entfernt, so dass es keine Zyklen gibt, die eine wichtige Stadt enthalten.Einschränkungen
1 ≤ T ≤ 20
1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ K ≤ NBeispiel
Im ersten Beispiel haben wir N = 5 Städte, die mit M = 7 verbunden sind Straßen und die Städte 0 und 1 sind wichtig. Wir können zwei Verbindungsstraßen entfernen (0, 1) und (1, 2) und das verbleibende Netzwerk enthält keine Zyklen mit wichtige Städte. Beachten Sie, dass es im verbleibenden Netzwerk einen Zyklus gibt enthält nur unwichtige Städte, und dazu gibt es auch mehrere Möglichkeiten Entferne zwei Straßen und erfülle alle Bedingungen. Man kann nicht nur eine Straße entfernen und zerstöre alle Zyklen, die wichtige Städte enthalten.Beispieleingabe
1
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4
Also habe ich es mir so ausgedacht: Während wir die Grafik erstellen, haben wir ein separates Array, das Informationen darüber speichert, wie viele Nachbarn jede Stadt hat (== wie viele Straßen mit der Stadt verbunden sind). Im Beispielfall hat Stadt 0 2, Stadt 1 3 und so weiter. Nennen wir diese Zahlen einen "Stadtwert" einer bestimmten Stadt.
Nachdem wir die gesamte Eingabe erhalten haben, gehen wir durch die ganze Reihe von Stadtwerten, die nach Städten mit dem Wert 1 suchen. Wenn man zu einem kommt, bedeutet das, dass es nicht in einem Zyklus sein kann, dekrementieren wir seinen Wert "löschen" ( ohne den Verlust der Allgemeinheit) die Straße, die sie mit ihrem einzigen Nachbarn verbindet und den Wert des Nachbarn herabsetzt. Danach gehen wir rekursiv zum Nachbar, der nach der gleichen Sache sucht, wenn der Wert 1 dort ist - wiederhole das Schema und gehe rekursiv tiefer. Wenn es nicht ist - nicht berühren.
Nach dieser Operation haben wir alle Teile des Graphen gelöscht, die keine Zyklen sind und nicht Teil eines sein können. Wir haben auch alle Straßen beseitigt, die keinen Sinn ergeben. Also rufen wir diesmal eine andere Funktion auf - arbeiten nur an den wichtigen Städten. Also nehmen wir den Scheitelpunkt 1 - nach der Verwendung der im vorherigen Absatz beschriebenen Funktion kann sein Wert nicht 1 sein (da er durch die Funktion bereits zu Null gemacht worden wäre), also ist es entweder 0 oder etwas & gt; 1. Im ersten Fall müssen wir nichts tun. In letzterem müssen wir den Wert 1 machen, indem wir Wert-1-Entfernungen durchführen. Ähnlich wie im vorherigen Absatz dekrementieren wir nach jeder Entfernung den Wert sowohl dieser Stadt als auch ihres Nachbarn und entfernen die Straße. Wir wiederholen es für alle wichtigen Städte, die die Wert-1-Werte aus allen wichtigen Städten zusammenfassen, und das ist unsere Antwort.
Macht es Sinn? Bei all den Tests, die ich versucht habe, hat es funktioniert und ich würde gerne glauben, dass es korrekt ist, aber irgendwie habe ich das Gefühl, dass irgendwo ein Leck sein könnte. Könnten Sie das bitte prüfen? Taugt es etwas? Wenn nicht, warum und ist irgendetwas an diesem Denkprozess korrekt? :)
3 Antworten
Wenn Sie beweisen können, dass die optimale Anzahl an Schnitten gleich der Anzahl der verschiedenen Zyklen * ist, die einen wichtigen Knoten enthalten, ist die Lösung des Problems nicht so schwierig.
Sie können ein DFS machen, die besuchten Knoten im Auge behalten, und wann immer Sie einen Knoten erreichen, den Sie bereits besucht haben, haben Sie einen Zyklus bekommen. Um festzustellen, ob der Zyklus einen wichtigen Knoten enthält oder nicht, verfolgen Sie die Tiefe, mit der jeder Knoten besucht wurde, und merken Sie sich die Tiefe des letzten wichtigen Knotens im aktuellen Zweig der Suche. Wenn die Starttiefe des Zyklus geringer (d. H. Früher) als die Tiefe des letzten wichtigen Knotens ist, enthält der Zyklus einen wichtigen Knoten.
C ++ - Implementierung:
%Vor%
* Mit 'anders' meine ich, dass ein Zyklus nicht gezählt wird, wenn alle seine Kanten bereits Teil verschiedener Zyklen sind. Im folgenden Beispiel betrachte ich die Anzahl der Zyklen als 2, nicht als 3:
%Vor%Mein Algorithmus basiert auf der folgenden Beobachtung: Da uns Zyklen nur mit unwichtigen Knoten egal sind, können unwichtige Knoten kollabiert werden. Wir kollabieren zwei benachbarte unwichtige -Knoten, indem wir sie durch einen einzelnen unwichtigen -Knoten mit der Summe der Kanten der ursprünglichen Knoten ersetzen.
Beim Zusammenlegen von zwei unwichtigen Knoten müssen wir zwei spezielle Fälle behandeln:
- Beide Knoten wurden mit demselben unwichtigen Knoten U verbunden. Dies bedeutet, dass es im ursprünglichen Graphen einen Zyklus von unwichtigen Knoten gab; Wir können den Zyklus ignorieren und der neue Knoten wird mit einer einzigen Kante mit demselben unwichtigen Knoten U verbunden.
- Beide Knoten wurden mit demselben wichtigen Knoten I verbunden. Dies bedeutet, dass es einen Zyklus von unwichtigen Knoten und den einzelnen wichtigen Knoten I im ursprünglichen Diagramm gab. vor dem Kollabieren der Knoten müssen wir eine der Kanten entfernen, die sie mit dem wichtigen Knoten I verbinden und so den Zyklus entfernen. Der neue Knoten wird über eine einzige Kante mit dem wichtigen Knoten I verbunden.
Mit der obigen Definition des Knotens kollabieren lautet der Algorithmus:
- Reduzieren Sie benachbarte unwichtige -Knoten, bis keine benachbarten unwichtigen -Knoten mehr vorhanden sind. Alle entfernten Kanten zwischen wichtig und unwichtigen Knoten, wie in Fall (2) oben definiert, zählen zur Lösung.
- Suchen Sie den Spanning Tree des verbleibenden Graphen und entfernen Sie alle Kanten, die nicht im Spanning Tree enthalten sind. Alle in diesem Schritt entfernten Kanten zählen zur Lösung.
Der Algorithmus läuft in O (M) Zeit. Ich glaube, ich kann seine Richtigkeit beweisen, würde aber gerne Ihr Feedback bekommen, bevor ich zu viel Zeit damit verbringe: -)