#P3396. [Usaco2009 Jan]Total flow 水流
[Usaco2009 Jan]Total flow 水流
[USACO 2009 Jan] Total Flow 水流
题目描述
农场有 根水管,约翰想计算从水井 A 到牛棚 Z 的最大流量。水管网络可以用以下规则简化:
串联:流量上限等于两根水管流量上限中的较小值。
+---5---+---3---+ -> +---3---+
并联:流量上限等于两根水管流量上限之和。
+---5---+
---+ +--- -> +---8---+
+---3---+
如果某根水管的一端通往死路,可将它移除。
+---5---+
---+ -> +---3---+
+---3---+--
原赛数据保证,给定的管网能通过这些规则简化为一根连接水井和牛棚的等效水管。
输入格式
从标准输入读入。第一行是一个整数 。接下来 行,每行两个字母 和一个整数 ,表示一根连接这两个端点的无向水管,流量上限为 。两个端点的书写先后不表示水流方向。
输出格式
向标准输出输出一行一个整数,表示从水井到牛棚的最大流量。
5
A B 3
B C 3
C D 5
D Z 4
B Z 6
3
样例解释
样例的管网和简化过程如下。
+-----------6-----------+
A+---3---+B +Z
+---3---+---5---+---4---+
C D
合并串联的 BC 和 CD。
+-----------6-----------+
A+---3---+B +Z
+-----3-----+-----4-----+
D
合并串联的 BD 和 DZ。
+-----------6-----------+
A+---3---+B +Z
+-----------3-----------+
合并两根并联的 BZ。
B
A+---3---+---9---+Z
最后将 AB 与合并后的 BZ 串联,总流量为 。
A+---3---+Z
数据范围与约定
,。每根水管的两个端点不同,均以英文字母表示,大小写是不同的端点。