Farmer John quiere suficiente agua para las vacas y dibuja las $N$ tuberías ($1 \le N \le 700$) entre pozo y establo. Descubre una red desordenada de tamaños variados y quiere calcular el flujo.
Dos tuberías en serie permiten el mínimo de sus capacidades. Capacidades 5 y 3 equivalen a una tubería de 3:
+---5---+---3---+ -> +---3---+
En paralelo las capacidades se suman:
+---5---+
---+ +--- -> +---8---+
+---3---+Una tubería sin más conexiones se elimina: no contribuye al flujo total:
+---5---+
---+ -> +---3---+
+---3---+--Todos los laberintos se reducen con estas reglas a una capacidad total.
Dado el mapa, halla la capacidad entre pozo (A) y establo (Z).
Ejemplo con nodos nombrados por letras:
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC y CD se combinan:
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD y DZ se combinan:
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+Las dos ramas de BZ se combinan:
B
A+---3---+---9---+ZAB y BZ se combinan para dar capacidad neta 3:
A+---3---+Z
Programa la lectura de tuberías descritas por dos extremos y calcula de 'A' a 'Z'. Todas las redes de prueba se reducen con estas reglas.
La tubería $i$ conecta nodos distintos $a_i$, $b_i$ (cada uno en 'A-Za-z') y flujo $F_i$ ($1 \le F_i \le 1,000$). Mayúsculas y minúsculas son nodos diferentes.
Las primeras 50 entregas reciben información adicional de pruebas.
Entrada
- Línea 1: entero $N$.
- Líneas $2,\ldots,N+1$: la línea $i+1$ describe tubería $i$ con dos letras y un entero separados por espacios: $a_i$, $b_i$, $F_i$.
Salida
- Línea 1: entero, flujo máximo del pozo ('A') al establo ('Z').
Ejemplos
Entrada 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Salida 1
3
Autor del problema: Rob Kolstad, 2008