1994 ACM Student Programming Contest

Pacific Region

Problem C: Resistor Networks

Let R1 and R2 be the resistance of two resistors.  If the
two resistors are connected in series, their effective
resistance is (R1+ R2).  If the two resistors are connected
in parallel, their effective resistance is (R1*R2)/(R1+ R2).

In general, suppose a network of resistors connects N nodes
in such a way that current will flow from node 1 to node N.
Then the above rules can be applied to compute the effective
resistance between nodes 1 and N.  As an example, the
network below contains 3 nodes connected by 4 resistors:

                             R1: 40.0 ohms
             --------------------XXXXX--------------------
            |                                             |
            |                      R3: 30.0 ohms          |
1 ----------                      -----XXXXX-----         |
            | R2: 10.0 ohms      |               |        |
             -----XXXXX-----2----                 -------------- 3
                                 |               |
                                  -----XXXXX-----
                                   R4: 20.0 ohms

The effective resistance from node 1 to node 3 can be
computed as follows:

1.  The effective resistance from node 2 to node 3 is given by
     (30.0*20.0)/(30.0+20.0) =12.0 ohms.
     
2.  The effective resistance from node 1 to node 3 along the
    lower path is given by
     (10.0+12.0) = 22.0 ohms.
     
3.  The effective resistance from node 1 to node 3 is given by
     (40.0*22.0)/(40.0+22.0) =14.2 ohms,
    to the nearest tenth of an ohm.

Your task is to write a program which will read in the
description of a network with N>=2 nodes and R<=20 resistors
and compute the effective resistance from node 1 to node N.
The resistors will be connected in such a way that current
will flow from node 1 to node N and will flow through every
resistor in the network.

INPUT.  The input will consist of a line containing the
number of nodes N, a second line containing the number of
resistors R, and R resistor lines.  Each resistor line
describes one resistor as follows:  beginning node; ending
node; resistance.  All input values will be positive
integers, except resistances in ohms will be positive reals
with one digit to the right of the decimal point.

The input for the above example network would therefore be

3
4
1  3  40.0
1  2  10.0
2  3  30.0
2  3  20.0

OUTPUT.  The output of your program is to be a set of lines
similar to those shown below echoing the total number of
nodes, number of resistors, resistance(s) between each node,
and finally the equivalent resistance of the network (the
effective resistance between nodes 1 and N).  All
resistances must be printed to the nearest tenth of an ohm,
including the computed effective resistance from node 1 to
node N.  For the above input, the required output (apart
from minor variations in the number of blanks) is as
follows:

nodes = 3
resistors = 4
node 1 to node 3:   40.0
node 1 to node 2:   10.0
node 2 to node 3:   30.0
node 2 to node 3:   20.0

equivalent resistance = 14.2