Farmer John vuole abbastanza acqua per le mucche e mappa gli $N$ tubi ($1 \le N \le 700$) tra pozzo e stalla. Scopre una rete disordinata di dimensioni varie e vuole calcolare il flusso.
Due tubi in serie consentono il minimo delle capacità. Capacità 5 e 3 equivalgono a un tubo 3:
+---5---+---3---+ -> +---3---+
In parallelo le capacità si sommano:
+---5---+
---+ +--- -> +---8---+
+---3---+Un tubo senza altre connessioni si elimina: non contribuisce al totale:
+---5---+
---+ -> +---3---+
+---3---+--Tutti i labirinti si riducono con queste regole a una sola capacità totale.
Dalla mappa trova la capacità tra pozzo (A) e stalla (Z).
Esempio con nomi di nodi a lettere:
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC e CD si combinano:
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD e DZ si combinano:
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+I due rami di BZ si combinano:
B
A+---3---+---9---+ZAB e BZ si combinano per una capacità netta 3:
A+---3---+Z
Scrivi un programma che legge tubi descritti da due estremi e calcola da 'A' a 'Z'. Tutte le reti di test si riducono con queste regole.
Tubo $i$ collega nodi distinti $a_i$, $b_i$ (ciascuno in 'A-Za-z') con flusso $F_i$ ($1 \le F_i \le 1,000$). Maiuscole e minuscole sono nodi diversi.
Le prime 50 submission ricevono informazioni aggiuntive sui test.
Input
- Riga 1: intero $N$.
- Righe $2,\ldots,N+1$: la riga $i+1$ descrive tubo $i$ con due lettere e un intero separati da spazi: $a_i$, $b_i$, $F_i$.
Output
- Riga 1: intero, flusso massimo dal pozzo ('A') alla stalla ('Z').
Esempi
Input 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Output 1
3
Autore del problema: Rob Kolstad, 2008