计算电压[洛谷P2011]

题目背景

相信不少人轻松灭掉 1,2 两题(蒟蒻无视此句) ,我相信,大家对物理也是很有兴趣的(众人:我们对揍人也是很有兴趣的) ,那么,再奉上 100 分给Physicaler 们。

题目描述

现给定一个电阻网络,已知其中每条边上的电阻,和若干个点和负极之间的电压(电源电压不变) ,现在求任意两点之间的电压。

输入格式

第一行三个数n,m,k,q,表示n个节点(可能是几个点用导线相连接,与一个点等价,编号为1-n,0号节点为电源负极),m个定值电阻,每个定值电阻连接两个点,k表示电源正极有k个接口,有q个询问。

以下k行,每行两整数,表示电源这k个正极的编号与该接线柱与电源负极负极之间的电压Ui。

以下m行,每行三个数,Vi,Wi,Ri,表示Ui与Vi之间添加一条阻值为R的电阻丝。

以下q行,每行两个整数Ai,Bi,表示要求Ai Bi之间的电压。

输出格式

q 行,每行一个实数,保留小数点后两位。(若 A 点电压低于 B 点,输出负值)

输入输出样例

输入 #1

输出 #1

说明/提示

【数据范围】

对于10%的数据,q=1;

对于20%的数据,1≤n≤10,保证电路为串联,并联或混联;

对于40%的数据,1≤n≤40,k≤5;

对于100%的数据,1≤k≤n≤200,1≤m≤200,000,1≤Ri,Ui≤10,000,1≤q≤1,000,000.

【限制】

时间限制:2s,内存限制:256M

【注释】

样例如图所示


\(首先先把电源负极定义为n+1,根据基尔霍夫方程组,对每个结点u,有第u个方程\)

\(若u是电源正极,那么方程为\varphi_{u}-\varphi_{n+1}=U\)

\(若u不是电源正极,那么方程为\sum_{u, v}\frac{\varphi_{u}-\varphi_{v}}{R_{u, v}}=0\)

\(若u是电源负极,那么方程为\varphi_{n+1}=0\)

\(总共n+1个方程,n+1个未知数,用高斯消元就可以解决\)


发表评论