P2011计算电压题解

· · 题解

（Update：修改了乘号）

1道电学好题

前置知识：高斯消元

分析

观察样例：

对于一个 Q（比如图中的②）：令电流流入 Q 的节点记为 A_i； 电流流出 Q 的节点为 B_i。容易知道：

\sum_{Ai}I_A=\sum_{Bi}I_B

(流入的电流之和等于流出的电流之和)

因为：

所以： $\sum_{Ai}\frac{U_A}{R_A}=\sum_{Bi}\frac{U_B}{R_B}

（这里的 U 和 R 指的是 A_i 或 B_i 到 Q 这段导体的电压和电阻，因为我们习惯于考虑一段电阻而不是两个点的电势差）

如果你学习过一定高中物理，你会知道电压其实就是两个位置之间电势的差值，所以设节点 $i$ 的电势为 $curU_i$ 则 $U=\vert curU_i-curU_Q \vert

式子变成：

\sum_{A_i}\frac{curU_A-curU_Q}{R_A}=\sum_{Bi}\frac{curU_Q-curU_B}{R_B}

移项：

\sum_{A_i}\frac{curU_A-curU_Q}{R_A}+\sum_{Bi}\frac{curU_B-curU_Q}{R_B}=0

令S_i=A_i\cup B_i即：

\sum_{S_i}\frac{curU_S-curU_Q}{R_S}=0

于是你惊喜地发现：不需要判断电流方向了！

但知道这个式子有什么用呢？

解决（代码）

由式子想到列方程（高斯消元），设每个点的电势为未知量，讯问时直接作差即可

变形：

\sum_{S_i}curU_S \times \frac{1}{R_S} - curU_Q \times \sum_{S_i}\frac{1}{R_S}=0

所以如果节点 A 与 Q 直接相连，那么在以 curU_Q 主元的方程中 curU_A 的系数为 \frac{1}{R_A}

而对于以 curU_Q 主元的方程，curU_Q的系数为 -\sum_{S_i}\frac{1}{R_S}

核心代码（带注释）：

for(register int i=1;i<=m;i++)
{
    int u,v;db w;
    u=read(),v=read(),w=read();
    add(u,v,w),add(v,u,w);//建立电路图
}
//列方程（核心）
for(register int i=1;i<=n;i++)
{
    if(st[i])   k[i][i]=1,k[i][n+1]=st[i];
    //st[i]是正电极电势
    //如果是正电极那么方程直接为 1*U[i]=st[i]
    else
    {
        db sum=0;
        for(int j=head[i];j;j=Edge[j].nxt)
        {
            int v=Edge[j].v;db w=Edge[j].w;
            k[i][v]+=1.0/w;//注意可能两点间有多个电阻
            sum+=1.0/w;
        }
        k[i][i]=-sum;//主元的系数
    }
}
gouse();//自行添加

正确性：每个未知量都有主元的方程（即一共 n 个），肯定能解出来

时间复杂度：O(能过)

列方程 O(n+m) 高斯消元O( n^3 )总：O(n^3+m)

制作不易，望管理员大大通过（这道题还没有较为详细的题解）

QwQ 完结撒花~~~