版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [Luogu P2011] 计算电压" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• 洛谷
• 数学
• 物理
• Kirchhoff定律
• Kirchhoff第一定律(KCL)
• 线性方程组
• Gauss消元 date: 2021-10-30 00:29:57

题目链接

原始题面

题目背景

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

题目描述

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

输入输出格式

输入格式

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

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

以下 $m$ 行, 每行三个数, $V_i,W_i,R_i$, 表示 $U_i$ 与 $V_i$ 之间添加一条阻值为 $R$ 的电阻丝

以下 $q$ 行, 每行两个整数 $A_i,B_i$, 表示要求 $A_i$ $B_i$ 之间的电压

输出格式

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

输入输出样例

输入样例 #1

3 5 1 3
1 18
1 2 6
1 3 2
2 3 6
3 0 6
2 0 2
1 0
2 3
1 2

输出样例 #1

18.00
-6.00
12.00

说明

【数据范围】

对于 $10\%$ 的数据, $q=1$

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

对于 $40\%$ 的数据, $1\leq n\leq 40,k\leq 5$

对于 $100\%$ 的数据, $1\leq k\leq n\leq 200,1\leq m\leq 200,000,1\leq R_i,U_i\leq 10,000,1\leq q\leq 1,000,000$

【限制】

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

【注释】

样例如图所示

解题思路

首先 % 罗神

显然直接用 Kirchhoff 第一定律 (KCL) 即可, 设

• 点 $i$ 的电势为 $\varphi_i$
• 已知电势的点 (即与电源正负极直接相连的点) 的指标集为 $\Lambda$
• 电阻网络构成的图为 $G$

则有

$$ \begin{cases} \varphi_i=Ui,&i\in\Lambda\ \displaystyle\sum{\lang i,j\rang\in G}{\varphi_i-\varphij\over R{ij}}=0,&i\notin\Lambda \end{cases} $$

另外注意两点

• 加电阻时候是并联, 所以不用处理重边
• 原题的部分数据点有错误 (截至笔者撰此文前), 详见 此处

复杂度

$O(n^3+m+q)$

代码参考