题解：SP2415 RESIST - Kirchhof Law

· · 题解

题意简述

给定一张 n 个节点 m 条边的无向图，边权表示电阻阻值，求节点 1 到 n 的等效电阻。

参考资料

解题思路

设节点 x 的电势为 \varphi_x，边 (u,v) 的电阻为 R_{u,v}，则电导为：

G_{u,v}=\frac{1}{R_{u,v}}

根据 欧姆定律，从 u 到 v 的电流为：

I_{u,v}=\frac{\varphi_u-\varphi_v}{R_{u,v}}=G_{u,v}(\varphi_u-\varphi_v)

根据 基尔霍夫电流定律，对于任意一个普通节点，所有关联支路电流的代数和为 0。

考虑节点 u 的电流：

\sum_{(u,v)\in E}I_{u,v}=\sum_{(u,v)\in E}G_{u,v}(\varphi_u-\varphi_v)=0

展开可得：

\left(\sum_{(u,v)\in E}G_{u,v}\right)\varphi_u-\sum_{(u,v)\in E}G_{u,v}\varphi_v=0

这是一个关于各点电势的线性方程。

a_{u,1}\varphi_1+a_{u,2}\varphi_2+\dots+a_{u,n}\varphi_n=b_u

考虑添加一条边 (u,v)，设其电导为 G。节点 u 的方程加入 G(\varphi_u-\varphi_v)，节点 v 的方程加入 G(\varphi_v-\varphi_u)，因此对应到系数矩阵就是：

a_{u,u}\gets a_{u,u}+G a_{u,v}\gets a_{u,v}-G a_{v,v}\gets a_{v,v}+G a_{v,u}\gets a_{v,u}-G

把所有边的贡献都加到矩阵里，就得到了整个线性方程组。

我们可以在节点 1 通入 1\mathrm{A} 电流，并将节点 n 设为零电势点，求出节点 1 的电势。

b_1=1,\varphi_n=0

利用 高斯消元 求解各点电势后，等效电阻为：

R=\frac{U}{I}=\frac{\varphi_1-\varphi_n}{1}=\varphi_1

参考代码

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-8;
const int N=105;
double a[N][N];
bool gauss(int n)
{
    for(int i=1;i<=n;i++)
    {
        int t=i;
        for(int j=i+1;j<=n;j++)
        {
            if(fabs(a[j][i])>fabs(a[t][i]))t=j;
        }
        if(fabs(a[t][i])<eps)return 0;
        swap(a[i],a[t]);
        for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i];
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            for(int k=n+1;k>i;k--)a[j][k]-=a[i][k]*a[j][i];
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    while(cin>>n>>m)
    {
        while(m--)
        {
            int u,v;
            double r;
            cin>>u>>v>>r;
            double g=1/r;
            a[u][u]+=g;
            a[u][v]-=g;
            a[v][v]+=g;
            a[v][u]-=g;
        }
        a[1][n+1]=1;
        for(int i=1;i<n;i++)a[n][i]=0;
        a[n][n]=1;
        a[n][n+1]=0;
        gauss(n);
        cout<<fixed<<setprecision(2)<<a[1][n+1]<<'\n';
        memset(a,0,sizeof a);
    }
    return 0;
}