MTOTALF - Total Flow


Để quản lý nước cho đàn bò, FJ  đã vẽ bản đồ đường ống gồm N (1<=N<=700) 
ống trong trang trại mà nối bể nước với các chuồng. FJ thấy rằng các 
đường ống có kích thước khác nhau và được nối một cách rất kỳ lạ. 
Do đó, FJ muốn tính xem lượng nước truyền qua các ống.

Hai ống nước được nối liên tiếp với nhau cho phép lượng nước không vượt 
quá thông lượng nhỏ nhất của hai ống. Một ống có thông lượng 5 nối với 
ống có thông lượng 3 sẽ tương đương với một ống có thông lượng 3.:

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

Còn hai ống nối song song cho phép thông lượng nước là tổng thông lượng 
của từng ống. 

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

Còn một ống mà không nối với chuồng bò nào hay ống nào khác có thể bỏ đi: 

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

Sử dụng cách thức trên, cho bản đồ đường ống, xác định lượng nước có thể
truyền từ nguồn (A) cho tới chuồng (Z).

Xét ví dụ sau:

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

Ống BC và CD có thể gộp lại được:

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

Sau đó gộp BD và DZ  :

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

Gộp hai nhánh nối B và Z:

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

Gộp AB và BZ và thông lượng thu được là 3:

        A+---3---+Z

FJ cần viết một chương trình đọc vào một tập các đường ống mà mỗi
đường ống được mô tả thông qua 2 đầu nối và tính thông lượng từ 'A' tới 'Z'.

Mọi dữ liệu cần tính đều có thể suy luận theo các quy tắc bên trên. 

Ống i nối hai nút a_i và b_i (a_i,b_i là các chữ cái hoa hoặc thường
 - 'A-Za-z') và có thông lượng F_i (1 <= F_i <= 1,000). 
Tên nút phân biệt chữ cái hoa và thường ('A' <> 'a').

INPUT

* Dòng 1: Số nguyên N

* Dòng 2..N + 1: Dòng i+1 mô tả ống i qua hai chữ cái và một số nguyên,
cách nhau bởi 1 dấu trống: a_i, b_i, and F_i

Ví dụ:

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

OUTPUT

* Dòng 1: Lượng nước lớn nhất có thể truyền từ nguồn A tới chuồng Z.

Ví dụ:  
3
Note : luyện viết code module chính bài này <=15 dòng với C/C++! Có thể giải bằng capacity scaling.

hide comments
regularcoder: 2019-05-22 17:36:22

I read Baojun Wang's comment, but when I submitted my code with bidirectional pipes, I got AC.
PS: The "multiple pipes between same node" thing tripped me up a lot too :D

rishi_devan: 2016-05-16 21:27:06

Used Map to store Nodes as Integer indexes,
Used BFS to find augmenting path in each step of Ford Fulkerson's
Used adjacency matrix to store capacities, flows and residual capacities

Last edit: 2016-05-16 21:27:19
Sonu Sharma: 2015-08-30 12:47:56

:) there may be multiple pipe between same pair of nodes.. That's true.. take care of that.. got a WA..but accepted now! :D

Baojun Wang: 2015-08-29 08:14:12

No, pipes ain't bidirectional.

Mauro Persano: 2015-06-16 18:16:01

Stuff to look out for: 1. pipes are bidirectional; 2. multiple pipes between the same pair of nodes (thanks Gaurav); 3. lower-case node names (A-Za-z)

Last edit: 2015-06-16 18:25:03
i_am_looser: 2015-06-11 20:30:34

max flow problem ; )

Kanish: 2015-02-03 17:40:18

@Problem_Setter can you tell me where my solution is failing
solution id:-13591923

Last edit: 2015-02-03 18:07:32
Julian Waldby: 2014-05-23 18:15:32

Uday, "All networks in the test data can be reduced using the rules here." Your example can't be reduced with these rules, so it shouldn't show up in the test data.

Panagiotis Kostopanagiotis: 2013-02-01 22:37:39

"Note that lower- and upper-case node names are intended
to be treated as different."

take care of that...


Added by:~!(*(@*!@^&
Date:2009-02-15
Time limit:0.252s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:USACO JAN09 SILVER Division