Farmer John veut assez d’eau pour ses vaches et cartographie les $N$ tuyaux ($1 \le N \le 700$) reliant puits et étable. Il découvre un réseau désordonné de tailles variées et veut calculer le débit.
Deux tuyaux en série ont le minimum des deux capacités. Les capacités 5 et 3 donnent un tuyau équivalent de 3 :
+---5---+---3---+ -> +---3---+
En parallèle, les capacités s’additionnent :
+---5---+
---+ +--- -> +---8---+
+---3---+Un tuyau sans autre connexion peut être retiré : il ne contribue pas au débit total :
+---5---+
---+ -> +---3---+
+---3---+--Tous ces labyrinthes se réduisent ainsi à une capacité totale unique.
Avec la carte, trouvez la capacité entre le puits (A) et l’étable (Z).
Exemple où les nœuds portent des lettres :
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C DBC et CD se combinent :
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
DBD et DZ se combinent :
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+Les deux branches de BZ se combinent :
B
A+---3---+---9---+ZAB et BZ se combinent pour une capacité nette de 3 :
A+---3---+Z
Programmez la lecture de tuyaux décrits par deux extrémités et le calcul de 'A' à 'Z'. Tous les réseaux testés se réduisent avec ces règles.
Le tuyau $i$ relie deux nœuds distincts $a_i$, $b_i$ (chacun dans 'A-Za-z') et a le débit $F_i$ ($1 \le F_i \le 1,000$). Majuscules et minuscules désignent des nœuds différents.
Les 50 premières soumissions reçoivent des informations supplémentaires sur les tests.
Entrée
- Ligne 1 : entier $N$.
- Lignes $2,\ldots,N+1$ : la ligne $i+1$ décrit le tuyau $i$ par deux lettres et un entier séparés par des espaces : $a_i$, $b_i$, $F_i$.
Sortie
- Ligne 1 : entier, débit maximal du puits ('A') à l’étable ('Z').
Exemples
Entrée 1
5 A B 3 B C 3 C D 5 D Z 4 B Z 6
Sortie 1
3
Auteur du problème : Rob Kolstad, 2008