OI题库

【题目描述】

在物理学中，我们常常对一些复杂的电路问题十分头疼，为了便于分析，我们需要把一些电阻的混连电路，用一个等效电阻来取代。而等效电阻的计算往往是十分繁琐的。于是，我们尝试用程序代替我们完成这项任务。程序需要计算的，是一个纯电阻的混连电路中两点间的总电阻。

为了阐述方便，我们建立这样一个模型来描述电路：电路由一个一个结点连接构成，结点就是导线的交点，若两结点间的电路上不存在其它结点，则称这两个结点是两相邻结点。两相邻结点之间只允许有两种情况：

（1）它们之间是一个已知电阻（如图1）：

（2）它们之间是x个已知电阻的纯并联电路（如图2）：

输入保证两相邻结点间总电阻不为零。

此模型必然可以描述所有的纯电阻电路。

【输入格式】

第一行是两个整数N，M。表示结点数为N，电路中共有M个电阻；

以下M行每行有三个整数，i,j和k（1≤i＜j≤N），表示结点i和结点j之间连结着大小为k的电阻（若i,j出现多次，则代表这两个节点之间并联多个电阻）。

【输出格式】

仅需输出一个数，就是结点a和结点b间的总电阻。输出保留二位小数。

【样例输入】

5 4
1 2 1
2 3 1
3 4 1
4 5 1

【样例输出】

4.00

【提示】

对于30%的数据，N<=10，M<=50

对于100%的数据，N<=200，M<=50000

【来源】

《电脑爱好者》1999年第12期

杨江明，《论数学策略在信息学问题中的应用》，IOI2000国家集训队论文集