The resistance of a circuit
A circuit of n nodes and m resistors has a V-volt battery connected to nodes s and t: plus to s, minus to t. Find the resistance of the circuit between s and t, how many times the battery’s voltage exceeds the current it delivers, and the largest current among all the resistors.
A resistor of resistance R between nodes with potentials φa and φb carries the current (φa − φb)/R; at every node except s and t, as much current flows out as flows in. There may be several resistors between two nodes, a resistor may connect a node to itself, and part of the circuit may not be connected to the battery at all.
The third test is the streets around Republic Square in Almaty (OpenStreetMap, ODbL): each street is a wire with a resistance of 1 ohm per 100 metres.
Input
The first line holds n, m, s, t, V (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ s, t ≤ n, s ≠ t, 0 < V ≤ 1000). Then come m lines a b R: a resistor between nodes a and b, 1 ≤ R ≤ 10⁶ ohms.
Output
Two numbers: the resistance of the circuit between s and t in ohms and the largest current in amperes. If current from the battery does not reach t, print -1 0. Numbers are accepted with a relative error of up to 10⁻⁶ (for numbers less than one, an absolute error).
Examples
Example 1
4 5 1 4 9 1 2 100 1 3 220 2 4 330 3 4 150 2 3 470
191.0441843 0.02737084515
Example 2
6 5 1 3 12 1 2 100 1 2 100 2 3 50 3 3 10 5 6 1000
100 0.12
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The unknowns are the potentials of the nodes. How many equations does Kirchhoff’s law give, and how many of them are independent?
2Hint 2
The potentials are defined only up to a common constant. What if one node is declared “ground”? And what to do with nodes that the battery’s current does not reach at all, as in the second example?
3The idea
Feed a current of 1 A into s and take it out of t, and take the potential of t as zero. For the other nodes Kirchhoff’s law gives a system with a Laplacian matrix: on the diagonal the sum of the conductances 1/R of all the node’s resistors, off the diagonal minus the conductance between neighbours (parallel resistors add up). Then the potential of s is the resistance of the circuit: volts per ampere. The circuit is linear, so the real potentials with a V-volt battery are these same ones multiplied by V/R.
But the system can only be solved for the nodes connected to s. A node that no resistor from the battery reaches is tied to ground by nothing, its potential can be anything, and the matrix is singular: Gaussian elimination will run into a zero pivot.
4Walkthrough
A depth-first search from s finds the connected part of the circuit. If t is not in it, no current flows: the answer is -1 0. Otherwise number the nodes of this part except t, build the matrix and the right-hand side with a one in row s, and solve by Gaussian elimination; for such a matrix pivoting is not required, but it does no harm. The resistance is the potential of s. Scale the potentials by V/R and go over the resistors of the connected part, computing |φa − φb|/R.
Tests with a known answer help to check yourself. A series chain: resistances add up, 1 + 2 + … + 199 = 19,900 ohms. Forty nodes, each joined to each through 100 ohms: between any two exactly 2·100/40 = 5 ohms.
4+Solution
5Complexity
The search is O(n + m), the matrix O(n²) memory, Gaussian elimination O(n³): with n = 200 that is about three million multiplications, a fraction of a second even in Python.
6Common mistakes
- Equations for all the nodes in a row. A pair of nodes hanging in the air makes the matrix singular: division by zero in the second test.
- No “ground”. The Laplacian of a connected circuit is singular by itself: its rows add up to zero. One node has to be removed by taking its potential as zero.
- Parallel resistors. Two resistors between one pair of nodes are a sum of conductances, not the last one read.
- A resistor “into itself”. It changes nothing: the potential difference across it is zero.