Problem Background

NOIP2018 Original Mock Test T7

NOIP2018 Original Mock Test DAY2 T2

NOIP DAY1 T2 or DAY2 T2 Difficulty Level

For relevant electrical knowledge, please refer to the "Background Knowledge" in the "Notes."

Problem Description

After examining a complex circuit diagram, you realize that the number of circuit components you learned in junior and senior high school is relatively small. Therefore, you wish to design a program to analyze circuit diagrams with a larger number of components and perform some calculations.

After much thought, you have finally found a method to describe the circuit diagram:

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

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

3. The most complex scenario in the circuit diagram is a parallel circuit nested within a series circuit. No more complex circuits will appear, such as the following cases:

For example, Sample 1 is a circuit diagram that meets the conditions (see the explanation for Sample 1 for the image).

Since this is your first attempt, you decide that the circuit will only include power sources and resistors, and you aim to calculate the maximum and minimum currents in the circuit.

After clarifying your thoughts, you decide to start trying.

Input Format

There are $m+1$ lines in total.

The first line contains two numbers $n, m$, representing the abstracted circuit diagram as a graph with $n$ nodes and $m$ edges.

The next $m$ lines, for each line:

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

The next character, if it is $'P'$, represents a power source with $x$ being the negative pole and $y$ being the positive pole. If it is $'R'$, it represents a resistor (without quotes).

The next number, if it is a power source, represents the voltage (in volts), otherwise, it represents the resistance (in ohms).

Output Format

Two lines:

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

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

3.00
1.50

Input Sample #2

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

Output Sample #2

11.00
2.00

Input Sample #3

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

Output Sample #3

7.11
2.37

Notes

Background Knowledge:

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

Series: In a series circuit, the current is equal, and the total resistance is the sum of the resistance values.

Parallel: In a parallel circuit, the voltage is equal.

Series-Parallel: A combination of series and parallel circuits.

Explanation for Sample 1:

As shown, the equivalent resistance of all resistors is $2Ω$, so the maximum current is $\frac{6V}{2Ω}=3A$. The current in branch $2-3$ or $2-4-3$ 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 in branch $1-4-3$. In Sample 3, the equivalent resistance of all resistors is $18Ω$.

Data Range:

For 30% of the data, there are: $n, m <= 20$

For 50% of the data, there are: $n <= 10^3, m <= 4 \times 10^3$

For 70% of the data, there are: $n <= 5000, m <= 2 \times 10^4$

For 100% of the data, there are:

1. $n <= 2 \times 10^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 irregularities.

3. The most complex scenario is a parallel circuit nested within a series circuit (as shown in Figure A, although there may be more branches and more resistors in series, branches will not have parallel connections), and it is guaranteed that there will be no parallel circuits nested within parallel circuits (as shown in Figure B, which will not occur).

Special Provisions:

20% of the data guarantees: The circuit is purely a series circuit.

Another 20% of the data guarantees: The circuit is purely a parallel circuit.

见题面 Input 部分

见题面 Output 部分