#P3396. [Usaco2009 Jan]Total flow 水流

[Usaco2009 Jan]Total flow 水流

[USACO 2009 Jan] Total Flow 水流

题目描述

农场有 NN 根水管,约翰想计算从水井 A 到牛棚 Z 的最大流量。水管网络可以用以下规则简化:

串联:流量上限等于两根水管流量上限中的较小值。

+---5---+---3---+    ->    +---3---+

并联:流量上限等于两根水管流量上限之和。

+---5---+
---+       +---    ->    +---8---+
   +---3---+

如果某根水管的一端通往死路,可将它移除。

+---5---+
---+               ->    +---3---+
   +---3---+--

原赛数据保证,给定的管网能通过这些规则简化为一根连接水井和牛棚的等效水管。

输入格式

从标准输入读入。第一行是一个整数 NN。接下来 NN 行,每行两个字母 ai,bia_i,b_i 和一个整数 FiF_i,表示一根连接这两个端点的无向水管,流量上限为 FiF_i。两个端点的书写先后不表示水流方向。

输出格式

向标准输出输出一行一个整数,表示从水井到牛棚的最大流量。

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 串联,总流量为 33。

A+---3---+Z

数据范围与约定

1≤N≤7001\le N\le700,1≤Fi≤1 0001\le F_i\le1\,000。每根水管的两个端点不同,均以英文字母表示,大小写是不同的端点。