MTOTALF - Total Flow


Farmer John always wants his cows to have enough water and thus has
made a map of the N (1 <= N <= 700) water pipes on the farm that
connect the well to the barn. He was surprised to find a wild mess
of different size pipes connected in an apparently haphazard way.
He wants to calculate the flow through the pipes.

Two pipes connected in a row allow water flow that is the minimum
of the values of the two pipe's flow values. The example of a pipe
with flow capacity 5 connecting to a pipe of flow capacity 3 can
be reduced logically to a single pipe of flow capacity 3:

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

Similarly, pipes in parallel let through water that is the sum of
their flow capacities:

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

Finally, a pipe that connects to nothing else can be removed; it
contributes no flow to the final overall capacity:

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

All the pipes in the many mazes of plumbing can be reduced using
these ideas into a single total flow capacity.

Given a map of the pipes, determine the flow capacity between the
well (A) and the barn (Z).

Consider this example where node names are labeled with letters:

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

Pipe BC and CD can be combined:

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

Then BD and DZ can be combined:

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

Then two legs of BZ can be combined:

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

Then AB and BZ can be combined to yield a net capacity of 3:

        A+---3---+Z

Write a program to read in a set of pipes described as two endpoints
and then calculate the net flow capacity from 'A' to 'Z'. All
networks in the test data can be reduced using the rules here.

Pipe i connects two different nodes a_i and b_i (a_i in range
'A-Za-z'; b_i in range 'A-Za-z') and has flow F_i (1 <= F_i <=
1,000). Note that lower- and upper-case node names are intended
to be treated as different.

INPUT

* Line 1: A single integer: N

* Lines 2..N + 1: Line i+1 describes pipe i with two letters and an
        integer, all space-separated: a_i, b_i, and F_i

SAMPLE INPUT  

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

OUTPUT

* Line 1: A single integer that the maximum flow from the well ('A')
        to the barn ('Z')

SAMPLE OUTPUT  

3

hide comments
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...

Santiago Palacio: 2012-03-15 03:05:19

Thank you Gaurav!!!!


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