SP2415 RESIST - Kirchhof Law

2026年3月6日 · 阅读需 3 分钟

题意简述

给定一张 $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;
}

题意简述​

参考资料​

解题思路​

参考代码​

题意简述

参考资料

解题思路

参考代码