题目背景

NOIP2018原创模拟题T7

NOIP2018原创模拟赛DAY2 T2

NOIP DAY1 T2 or DAY2 T2 难度

相关电学知识请参考“说明”中的“背景知识”。

题目描述

你看了复杂的电路图，发现在初高中学的电路元件数都目比较少，因此你希望设计一个程序来分析元件数目更多的电路图，并进行一些计算。

经过苦苦思考，你终于找到了描述电路图的方法：

1.电路图可以用$n$个节点，$m$条无向边的连通图来表示，其中$n$表示导线交汇点，$m$表示元件个数，且电路元件只有电源和电阻

2.图中没有自环，但可能有重边

3.电路图最复杂的情况是并联中嵌套串联，不会出现更复杂的电路，例如下面的情况都不会出现：

比如样例一便是一个满足条件的电路图（图片见样例一解释）

因为这是你第一次尝试，所以你决定电路中只包含电源与电阻，而且你决定计算电路中的最大电流与最小电流。

在理清思路后你就决定开始尝试了。

输入格式

共$m+1$行

第一行两个数 $n,m$，表示电路图抽象为$n$个节点，$m$条边的无向图

接下来$m$行，对于每一行：

前两个数为$x,y$，表示$x,y$之间有一个元件

接下来一个字符，如果为 $'P'$ 表示电源，且$x$方向为电源负极，$y$方向为电源正极，如果为 $'R'$ 表示电阻（均不含引号）

再接下来一个数字，如果为电源，表示电压（单位：伏特），否则表示电阻（单位：欧姆）

输出格式

两行

第一行输出最大电流值，保留两位小数

第二行输出最小电流值，保留两位小数

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

提示

背景知识：

欧姆定理：$I=\frac{U}{R}$，其中$I$为电流，$U$为电压，$R$为电阻

串联：串联电路中电流相等，总电阻相当于电阻阻值之和

并联：并联电路中电压相等

串并联：即串联与并联结合

样例一解释：

如图，所有电阻等效电阻为$2Ω$，故最大电流为$\frac{6V}{2Ω}=3A$，在支线$2-3$或$2-4-3$中电流为$1.5A$，为最小电流

样例二/三提示：

样例二中所有电阻的等效电阻阻值为$\frac{6}{11}Ω$，且最小电流在支线$1-4-3$上，样例三中所有电阻的等效电阻阻值为$18Ω$

数据范围：

对于 30%数据，有：$n,m<=20$

对于 50%数据，有：$n<=10^3,m<=4\times 10^3$

对于 70%数据，有：$n<=5000,m<=2\times10^4$

对于100%数据，有：

1.$n<=2\times10^4,m<=5\times 10^4$，$0<=$电压$<=10^8$，$1<=$电阻$<=10^3$

2.只有有一个电源，电路不会有不规范的地方

3.最复杂的情况为并联中嵌套串联（如图A，当然支路可能更多，电阻串联数量有可能更多，但支路不会出现并联），保证不会出现并联中再嵌套并联（如图B的情况就不会出现）

特殊约定：

20%数据保证：电路为纯串联电路

另外20%数据保证：电路为纯并联电路