题解 P4020 【[CTSC2012]电阻网络】
SuperJvRuo
2018-10-28 12:05:46
本篇题解符号约定：
| 物理量 | 符号 |
| ----------- | ----------- |
| 电流 | I |
| 电动势 | E |
| 电阻 | R |
| 电势差（电压） | U |
| 电势 | $\varphi$ |
这是一道电学题，我们复习一些电学内容：
### 1.欧姆定律
在同一电路中，通过某段导体的电流跟这段导体两端的电压成正比，跟这段导体的电阻成反比，即：
$$I=\frac{U}{R}$$
### 2.基尔霍夫第一定律
汇合于任一节点处的各电流的代数和等于0，即:
$$\sum I=\sum I_{in}+\sum I_{out}=0$$
对于一些电学题目，可以依据欧姆定律和基尔霍夫第一定律列出方程组，利用高斯消元求解。
但是这题数据范围50000，高斯消元只能获得30pts。我们注意到树上的最长链长度不超过50，应考虑由父亲到儿子或是儿子到父亲的递推关系，暴力递推答案。
显然，只要本题中所有的电阻器阻值相同，不论每个电阻的阻值是$10000\Omega$还是$0.1\Omega$，答案都是一样的。因此我将每个电阻的阻值记为$R$。为了便于计算，钦点一个叶子节点为根。
考虑节点$i$：
设$i$的父节点为$fa$，子节点集合为$son$，$fa$到$i$的电流为$I_i$。
由父节点$fa$到$i$的电路中，电阻处电势的下降，加上电源带来的电势上升，其结果就等于两点的电势差：
$$I_iR+E_i=\varphi_{fa}-\varphi_{i}$$
移项得：
$$I_i=\frac{\varphi_{fa}-\varphi_{i}-E_i}{R}$$
同理，由$i$到每个子节点$x$的电路中，都有：
$$I_xR+E_x=\varphi_{i}-\varphi_{x}$$
移项，对所有子节点求和得：
$$\sum_{x\in son}I_x=\sum_{x\in son}\frac{\varphi_{i}-\varphi_{x}-E_x}{R}$$
$i$点的基尔霍夫第一定律：
$$\sum_{x\in son}I_x=I_i$$
将已求得的两个$I$带入第三个式子：
$$\sum_{x\in son}\frac{\varphi_{i}-\varphi_{x}-E_x}{R}=\frac{\varphi_{fa}-\varphi_{i}-E_i}{R}$$
整理得：
$$\varphi_i=\frac{\varphi_{fa}-E_i+\sum_{x\in son}(\varphi_x+E_x)}{deg_i}$$
为了暴力递推，设$\varphi_i=K_i\varphi_{fa}+B_i$，其中$K_i$和$B_i$都是只与$i$与$son$有关的系数，将上式中的$\varphi_x$以这种形式表示，即得：
$$\varphi_i=\frac{\varphi_{fa}-E_i+\sum_{x\in son}(K_x\varphi_i+B_x+E_x)}{deg_i}$$
提出系数：
$$K_i=\frac{1}{deg_i-\sum_{x\in son}K_x}$$
$$B_i=\frac{\sum_{x\in son}(B_x+E_x)-E_i}{deg_i-\sum_{x\in son}K_x}=K_i(\sum_{x\in son}(B_x+E_x)-E_i)$$
豁然开朗了是不是？
诶不对啊，我们要求的是$i$到地面的电势差啊？我们还要思考一下接地节点的边界处理。
叶子节点$i$在原图中的度数为1，算上接地的一条边，度数为2。地面的电势为$0$。因此：
$$\varphi_i=\frac{\varphi_{fa}-E_i}{2}$$
故：
$$K_i=\frac{1}{2}$$
$$B_i=\frac{-E_i}{2}$$
这样，我们求得的$\varphi_i$就是$i$点到地面的电势差了。
$K$与电路中的电源无关，可以预处理直接求。加电源的时候暴力向上修改$B$即可。查询电势差的时候也是向上dark♂力扫一遍。由于链长不超过50，其复杂度完全正确。
```
#include<cstdio>
#include<cctype>
#include<algorithm>
struct Edge
{
int to,next;
}edge[100005];
int head[50005],cnt;
void Add_edge(int u,int v)
{
edge[++cnt]=(Edge){v,head[u]};
head[u]=cnt;
edge[++cnt]=(Edge){u,head[v]};
head[v]=cnt;
}
int root;
int degree[50005],fa[50005];
double k[50005],b[50005],sum_b[50005],U[50005],sum_u[50005];
void init_k(int u,int f)
{
fa[u]=f;
double sum_k=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v!=f)
{
init_k(v,u);
sum_k+=k[v];
}
}
k[u]=1.0/(degree[u]-sum_k);
}
void Add_b(int u,int e)
{
if(u==0)
return;
else
{
sum_b[fa[u]]-=b[u];
b[u]=(sum_b[u]+sum_u[u]-U[u])*k[u];
sum_b[fa[u]]+=b[u];
Add_b(fa[u],e);
}
}
void Modify(int u,int v,int e)
{
if(fa[v]==u)
{
std::swap(u,v);
e=-e;
}
U[u]+=e;
sum_u[v]+=e;
Add_b(u,e);
}
double Query(int u)
{
if(u==0)
{
return 0;
}
return k[u]*Query(fa[u])+b[u];
}
int main()
{
int n,m,u,v,e;
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i)
{
scanf("%d%d",&u,&v);
Add_edge(u,v);
++degree[u];
++degree[v];
}
for(int i=1;i<=n;++i)
{
if(degree[i]==1)
{
Add_edge(i,0);
degree[0]=1;
break;
}
}
for(int i=1;i<=n;++i)
{
if(degree[i]==1)
degree[i]=2;
}
init_k(0,0);
while(m--)
{
char ch=getchar();
while(!isalpha(ch))
{
ch=getchar();
}
if(ch=='Q')
{
scanf("%d",&u);
printf("%.12lf\n",Query(u));
}
else
{
scanf("%d%d%d",&u,&v,&e);
Modify(u,v,e);
}
}
return 0;
}
```