Farmer John chce dość wody dla krów i rysuje $N$ rur ($1 \le N \le 700$) łączących studnię z oborą. Dziwi się chaotycznej sieci różnych rozmiarów i chce obliczyć przepływ.
Dwie rury szeregowo przepuszczają minimum ich przepustowości. 5 i 3 są równoważne jednej rurze 3:
+---5---+---3---+ -> +---3---+
Równolegle przepustowości się sumują:
+---5---+
---+ +--- -> +---8---+
+---3---+Rurę bez dalszego połączenia można usunąć: nie wnosi nic do całości:
+---5---+
---+ -> +---3---+
+---3---+--Wszystkie labirynty rur da się tak zredukować do jednej przepustowości.
Z mapy znajdź przepustowość między studnią (A) a oborą (Z).
Przykład z literowymi nazwami węzłów:
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC i CD można połączyć:
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD i DZ można połączyć:
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+Dwie gałęzie BZ można połączyć:
B
A+---3---+---9---+ZAB i BZ dają przepustowość netto 3:
A+---3---+Z
Napisz program czytający rury opisane dwoma końcami i obliczający od 'A' do 'Z'. Wszystkie sieci testowe redukują się tymi regułami.
Rura $i$ łączy różne węzły $a_i$, $b_i$ (oba w 'A-Za-z') z przepływem $F_i$ ($1 \le F_i \le 1,000$). Małe i wielkie litery oznaczają różne węzły.
Pierwsze 50 zgłoszeń otrzymuje dodatkowe informacje o testach.
Wejście
- Wiersz 1: liczba całkowita $N$.
- Wiersze $2,\ldots,N+1$: wiersz $i+1$ opisuje rurę $i$ dwiema literami i liczbą całkowitą oddzielonymi spacjami: $a_i$, $b_i$, $F_i$.
Wyjście
- Wiersz 1: liczba całkowita, maksymalny przepływ ze studni ('A') do obory ('Z').
Przykład
Wejście 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Wyjście 1
3
Autor zadania: Rob Kolstad, 2008