Background

NOIP 2018 original mock problem T7.

NOIP 2018 original mock contest DAY 2 T2.

Difficulty: NOIP DAY 1 T2 or DAY 2 T2.

For related electrical knowledge, please refer to “Background Knowledge” in the “Hint” section.

Problem Description

After looking at a complex circuit diagram, you find that the number of circuit components studied in junior and senior high school is relatively small. Therefore, you want to design a program to analyze circuit diagrams with more components and perform some calculations.

After long thinking, you finally found a way to describe a circuit diagram:

1. A circuit diagram can be represented by a connected graph with $n$ nodes and $m$ undirected edges, where $n$ represents wire junctions, $m$ represents the number of components, and the circuit components are only power sources and resistors.

2. The graph has no self-loops, but it may have multiple edges.

3. The most complex case of the circuit is series connections nested inside parallel connections, and no more complex circuits will appear. For example, the following cases will not appear:

For example, Sample 1 is a circuit diagram that satisfies the conditions (see the picture in the explanation of Sample 1).

Since this is your first attempt, you decide that the circuit contains only power sources and resistors, and you decide to compute the maximum current and the minimum current in the circuit.

After sorting out your ideas, you decide to start trying.

Input Format

There are $m+1$ lines in total.

The first line contains two numbers $n,m$, meaning the circuit diagram is abstracted as an undirected graph with $n$ nodes and $m$ edges.

In the next $m$ lines, for each line:

The first two numbers are $x,y$, meaning there is a component between $x$ and $y$.

Then there is a character: if it is $'P'$ it means a power source, and the direction from $x$ to $y$ is from the negative terminal to the positive terminal; if it is $'R'$ it means a resistor (without quotes).

Then there is a number: if it is a power source, it indicates the voltage (unit: volt); otherwise it indicates the resistance (unit: ohm).

Output Format

Two lines.

The first line outputs the maximum current value, keeping two decimal places.

The second line outputs the minimum current value, keeping two decimal places.

4 5
1 2 P 6
2 3 R 2
3 4 R 1
2 4 R 1
1 3 R 1

3.00
1.50

4 6
1 3 P 6
1 3 R 1
1 2 R 1
2 3 R 1
1 4 R 1
4 3 R 2

11.00
2.00

16 21
1 2 R 2
2 3 R 1
3 4 R 1
2 5 R 1
4 5 R 1
4 6 R 1
6 7 R 1
7 8 R 2
4 9 R 1
8 9 R 1
1 16 P 128
10 8 R 7
10 11 R 2
11 10 R 1
11 12 R 2
12 15 R 1
15 13 R 2
11 13 R 1
11 14 R 1
14 15 R 2
15 16 R 5

7.11
2.37

Hint

Background Knowledge:

Ohm’s law: $I=\frac{U}{R}$, where $I$ is current, $U$ is voltage, and $R$ is resistance.

Series connection: in a series circuit, currents are equal, and the total resistance equals the sum of the resistances.

Parallel connection: in a parallel circuit, voltages are equal.

Series-parallel: a combination of series and parallel.

Explanation of Sample 1:

As shown, the equivalent resistance of all resistors is $2Ω$, so the maximum current is $\frac{6V}{2Ω}=3A$. In branch $2-3$ or $2-4-3$, the current is $1.5A$, which is the minimum current.

Hints for Sample 2/3:

In Sample 2, the equivalent resistance of all resistors is $\frac{6}{11}Ω$, and the minimum current is on branch $1-4-3$. In Sample 3, the equivalent resistance of all resistors is $18Ω$.

Constraints:

For $30\%$ of the testdata: $n,m<=20$.

For $50\%$ of the testdata: $n<=10^3,m<=4\times 10^3$.

For $70\%$ of the testdata: $n<=5000,m<=2\times10^4$.

For $100\%$ of the testdata:

1. $n<=2\times10^4,m<=5\times 10^4$, $0<=$ voltage $<=10^8$, $1<=$ resistance $<=10^3$.

2. There is only one power source, and the circuit will not have any irregular parts.

3. The most complex case is series connections nested inside parallel connections (like Figure A. Of course, there may be more branches, and the number of resistors in series may be larger, but a branch will not contain parallel connections). It is guaranteed that there will not be parallel connections nested inside parallel connections (cases like Figure B will not appear).

Special Notes:

For $20\%$ of the testdata, it is guaranteed that the circuit is a purely series circuit.

For another $20\%$ of the testdata, it is guaranteed that the circuit is a purely parallel circuit.

Translated by ChatGPT 5