MTOTALF - VNOI

MTOTALF - Total Flow

Giới hạn

Thời gian: 0.252s
Bộ nhớ: 1536MB
Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Để quản lý nước cho đàn bò, FJ đã vẽ bản đồ đường ống gồm N (1 <= N <= 700) ống trong trang trại mà nối bể nước với các chuồng. FJ thấy rằng các đường ống có kích thước khác nhau và được nối một cách rất kỳ lạ. Do đó, FJ muốn tính xem lượng nước truyền qua các ống. Hai ống nước được nối liên tiếp với nhau cho phép lượng nước không vượt quá thông lượng nhỏ nhất của hai ống. Một ống có thông lượng 5 nối với ống có thông lượng 3 sẽ tương đương với một ống có thông lượng 3:

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

Còn hai ống nối song song cho phép thông lượng nước là tổng thông lượng của từng ống.

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

Còn một ống mà không nối với chuồng bò nào hay ống nào khác có thể bỏ đi:

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

Sử dụng cách thức trên, cho bản đồ đường ống, xác định lượng nước có thể truyền từ nguồn (A) cho tới chuồng (Z).

Xét ví dụ sau:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

Ống BC và CD có thể gộp lại được:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

Sau đó gộp BD và DZ :

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

Gộp hai nhánh nối B và Z:

                 B
        A+---3---+---9---+Z

Gộp AB và BZ và thông lượng thu được là 3:

        A+---3---+Z

FJ cần viết một chương trình đọc vào một tập các đường ống mà mỗi đường ống được mô tả thông qua 2 đầu nối và tính thông lượng từ 'A' tới 'Z'.

Mọi dữ liệu cần tính đều có thể suy luận theo các quy tắc bên trên.

Ống i nối hai nút a_i và b_i (a_i,b_i là các chữ cái hoa hoặc thường - 'A-Za-z') và có thông lượng F_i (1 <= F_i <= 1,000). Tên nút phân biệt chữ cái hoa và thường ('A' <> 'a').

INPUT

Dòng 1: Số nguyên N
Dòng 2..N + 1: Dòng i+1 mô tả ống i qua hai chữ cái và một số nguyên, cách nhau bởi 1 dấu trống: a_i, b_i, and F_i

OUTPUT

Dòng 1: Lượng nước lớn nhất có thể truyền từ nguồn A tới chuồng Z.

VÍ DỤ

Input

5
A B 3
B C 3
C D 5
D Z 4
B Z 6

Output

Người up: vdmedragon
Nguồn bài: USACO JAN09 SILVER Division