Farmer John will genug Wasser für seine Kühe und zeichnet die $N$ Rohre ($1 \le N \le 700$) zwischen Brunnen und Stall. Über das chaotische Netz verschiedener Größen ist er überrascht und will den Durchfluss berechnen.
Zwei Rohre in Reihe erlauben das Minimum ihrer Kapazitäten. Kapazitäten 5 und 3 ergeben ein gleichwertiges Rohr 3:
+---5---+---3---+ -> +---3---+
Parallel addieren sich die Kapazitäten:
+---5---+
---+ +--- -> +---8---+
+---3---+Ein Rohr ohne weitere Verbindung kann entfernt werden: es trägt nichts zum Gesamtdurchfluss bei:
+---5---+
---+ -> +---3---+
+---3---+--Alle Rohrlabyrinthe lassen sich so auf eine einzige Gesamtkapazität reduzieren.
Bestimme anhand des Plans die Kapazität zwischen Brunnen (A) und Stall (Z).
Beispiel mit Buchstabennamen für Knoten:
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC und CD werden kombiniert:
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD und DZ werden kombiniert:
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+Die zwei BZ-Zweige werden kombiniert:
B
A+---3---+---9---+ZAB und BZ ergeben eine Nettokapazität von 3:
A+---3---+Z
Schreibe ein Programm, das Rohre mit zwei Endpunkten liest und die Kapazität von 'A' nach 'Z' berechnet. Alle Testnetze sind mit diesen Regeln reduzierbar.
Rohr $i$ verbindet verschiedene Knoten $a_i$, $b_i$ (je in 'A-Za-z') mit Fluss $F_i$ ($1 \le F_i \le 1,000$). Groß- und Kleinbuchstaben bezeichnen verschiedene Knoten.
Für die ersten 50 Einreichungen gibt es zusätzliche Testrückmeldungen.
Eingabe
- Zeile 1: ganze Zahl $N$.
- Zeilen $2,\ldots,N+1$: Zeile $i+1$ beschreibt Rohr $i$ mit zwei Buchstaben und einer ganzen Zahl, durch Leerzeichen getrennt: $a_i$, $b_i$, $F_i$.
Ausgabe
- Zeile 1: ganze Zahl, maximaler Fluss vom Brunnen ('A') zum Stall ('Z').
Beispiele
Eingabe 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Ausgabe 1
3
Aufgabenautor: Rob Kolstad, 2008