Farmer John quer água suficiente para as vacas e mapeia os $N$ canos ($1 \le N \le 700$) entre poço e celeiro. Descobre uma rede bagunçada de tamanhos variados e quer calcular o fluxo.
Dois canos em série permitem o mínimo das capacidades. Capacidades 5 e 3 equivalem a um cano 3:
+---5---+---3---+ -> +---3---+
Em paralelo, capacidades se somam:
+---5---+
---+ +--- -> +---8---+
+---3---+Um cano sem outras conexões pode ser removido: não contribui ao total:
+---5---+
---+ -> +---3---+
+---3---+--Todos os labirintos se reduzem por essas regras a uma única capacidade total.
Dado o mapa, calcule a capacidade entre poço (A) e celeiro (Z).
Exemplo com nomes de nós em letras:
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC e CD se combinam:
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD e DZ se combinam:
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+Os dois ramos de BZ se combinam:
B
A+---3---+---9---+ZAB e BZ se combinam para capacidade líquida 3:
A+---3---+Z
Programe a leitura dos canos descritos por duas pontas e calcule de 'A' a 'Z'. Todas as redes de teste se reduzem com essas regras.
Cano $i$ liga nós distintos $a_i$, $b_i$ (cada um em 'A-Za-z') com fluxo $F_i$ ($1 \le F_i \le 1,000$). Maiúsculas e minúsculas são nós distintos.
As primeiras 50 submissões recebem informação adicional sobre testes.
Entrada
- Linha 1: inteiro $N$.
- Linhas $2,\ldots,N+1$: a linha $i+1$ descreve cano $i$ com duas letras e um inteiro separados por espaços: $a_i$, $b_i$, $F_i$.
Saída
- Linha 1: inteiro, fluxo máximo do poço ('A') ao celeiro ('Z').
Exemplos
Entrada 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Saída 1
3
Créditos do problema: Rob Kolstad, 2008