UVa 345 It‘s Ir-Resist-Able

题目描述

电阻器是电子电路中的常见元件。每个电阻器有两个端子，当电流流过电阻器时，部分电流转化为热量，从而“抵抗”电流的流动。电阻器对电流的抵抗程度用一个正数值表示，称为电阻值，单位是欧姆（Ohms\texttt{Ohms}Ohms）。

当两个电阻器串联时，等效电阻等于各电阻值之和。当两个电阻器并联时，等效电阻的倒数等于各电阻倒数之和。

在本题中，给定一个电阻网络（由若干电阻器及其连接点组成），需要计算两个指定点之间的等效电阻。

输入格式

输入包含多个测试用例。每个测试用例以一行三个整数NNN、AAA、BBB开始：

• NNN：电阻器数量（不超过303030）
• AAA、BBB：需要计算等效电阻的两个端点标签

接下来NNN行，每行包含两个整数（连接点标签）和一个实数（电阻值）。

输入以N=A=B=0N = A = B = 0N=A=B=0结束。

输出格式

对于每个测试用例，输出一行，包含用例编号和等效电阻（保留两位小数），格式如样例所示。

样例输入

2 1 3 1 2 100 2 3 200 2 1 2 1 2 100 1 2 150 6 1 6 1 2 500 1 3 15 3 4 40 3 5 100 4 6 60 5 6 50 0 0 0

样例输出

Case 1: 300.00 Ohms Case 2: 60.00 Ohms Case 3: 75.00 Ohms

题目分析

问题的本质

这是一个电阻网络分析问题。给定一个由电阻器组成的网络，需要计算两个节点之间的等效电阻。由于电阻网络可能包含复杂的串并联组合（甚至更复杂的桥式结构），需要使用节点电压法（nodal analysis\texttt{nodal analysis}nodal analysis）结合基尔霍夫定律求解。

基尔霍夫定律

• 基尔霍夫电流定律（KCL\texttt{KCL}KCL）：流入任一节点的电流代数和为零
• 基尔霍夫电压定律（KVL\texttt{KVL}KVL）：任一回路中电压降的代数和为零

节点电压法

选取一个参考节点（电压为000），其他节点的电压为未知量。对于每个节点，根据KCL\texttt{KCL}KCL建立方程：

∑jVi−VjRij=0 \sum_{j} \frac{V_i - V_j}{R_{ij}} = 0j∑​Rij​Vi​−Vj​​=0

其中RijR_{ij}Rij​是节点iii和jjj之间的电阻（如果有多个电阻并联，需先合并）。

边界条件

在本问题中：

• 设起点AAA的电压为VA=1000V_A = 1000VA​=1000（任意正数）
• 设终点BBB的电压为VB=0V_B = 0VB​=0
• 其他节点的电压为未知量

求解过程

1. 建立节点电压方程组
2. 使用高斯消元法求解各节点电压
3. 计算从BBB节点流出的总电流III（或流入AAA的电流）
4. 等效电阻Req=(VA−VB)/IR_{eq} = (V_A - V_B) / IReq​=(VA​−VB​)/I

解题思路

步骤一：离散化节点标签

电阻器的连接点标签是任意正整数，需要映射到0∼C−10 \sim C-10∼C−1的连续索引。

map<int,int>indexer;for(inti=0;i<N;i++){cin>>X>>Y>>R;if(indexer.find(X)==indexer.end())indexer[X]=label++;if(indexer.find(Y)==indexer.end())indexer[Y]=label++;}

步骤二：合并并联电阻

对于同一对节点之间可能有多条并联电阻，需要先合并：

resistor[idxX][idxY]+=1.0/R;resistor[idxY][idxX]+=1.0/R;

计算等效电阻时，取倒数：

for(inti=0;i<C;i++)for(intj=0;j<C;j++)if(resistor[i][j]>0)resistor[i][j]=1.0/resistor[i][j];

步骤三：建立节点电压方程

对于每个节点（除AAA和BBB外），根据KCL\texttt{KCL}KCL建立方程：

∑jVi−VjRij=0 \sum_{j} \frac{V_i - V_j}{R_{ij}} = 0j∑​Rij​Vi​−Vj​​=0

整理得：

(∑j1Rij)Vi−∑j1RijVj=0 \left(\sum_{j} \frac{1}{R_{ij}}\right) V_i - \sum_{j} \frac{1}{R_{ij}} V_j = 0(j∑​Rij​1​)Vi​−j∑​Rij​1​Vj​=0

在矩阵中：

• 对角线元素matrix[i][i]减去1Rij\frac{1}{R_{ij}}Rij​1​
• 非对角线元素matrix[i][j]加上1Rij\frac{1}{R_{ij}}Rij​1​

步骤四：设置边界条件

对于AAA和BBB节点，其电压已知，不需要建立KCL\texttt{KCL}KCL方程。将它们的方程设为：

matrix[idxA][idxA]=1.0;matrix[idxB][idxB]=1.0;voltage[idxA]=1000.0;voltage[idxB]=0.0;

步骤五：高斯消元求解

使用列主元高斯消元法求解线性方程组Ax=bAx = bAx=b。

步骤六：计算总电流和等效电阻

从BBB节点计算流入的总电流：

doublecurrent=0.0;for(intnode=0;node<C;node++)if(resistor[node][idxB]>EPSILON)current+=(voltage[node]-voltage[idxB])/resistor[node][idxB];

等效电阻：

Req=(voltage[idxA]-voltage[idxB])/current;

参考代码

// It's Ir-Resist-Able!// UVa ID: 345// Verdict: Accepted// Submission Date: 2016-11-15// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100;constdoubleEPSILON=1e-8;// 不考虑其他连接点影响时，两个连接点间的阻值doubleresistor[MAXN][MAXN];// 各个连接点的电势doublevoltage[MAXN];// 列主元高斯消元法求解线性方程组 Ax = bboolgaussianElimination(vector<vector<double>>&A,vector<double>&b){intn=A.size();// 将 b 作为增广矩阵的最后一列for(inti=0;i<n;i++)A[i].push_back(b[i]);for(inti=0;i<n;i++){// 选取主元（绝对值最大的行）intpivot=i;for(intj=i;j<n;j++)if(fabs(A[j][i])>fabs(A[pivot][i]))pivot=j;swap(A[i],A[pivot]);// 矩阵奇异if(fabs(A[i][i])<EPSILON)returnfalse;// 将主元归一化for(intj=i+1;j<=n;j++)A[i][j]/=A[i][i];// 消去其他行的当前列for(intj=0;j<n;j++)if(i!=j)for(intk=i+1;k<=n;k++)A[j][k]-=A[j][i]*A[i][k];}// 提取解for(inti=0;i<n;i++)b[i]=A[i][n];returntrue;}intmain(intargc,char*argv[]){intN,A,B,X,Y,cases=0;doubleR;while(cin>>N>>A>>B,N>0){cout<<"Case "<<++cases<<": ";// 初始化电阻矩阵for(inti=0;i<MAXN;i++)for(intj=0;j<MAXN;j++)resistor[i][j]=0.0;// 离散化节点标签map<int,int>indexer;intlabel=0;for(inti=0;i<N;i++){cin>>X>>Y>>R;if(indexer.find(X)==indexer.end())indexer[X]=label++;if(indexer.find(Y)==indexer.end())indexer[Y]=label++;// 合并并联电阻：存储电导（1/R）resistor[indexer[X]][indexer[Y]]+=1.0/R;resistor[indexer[Y]][indexer[X]]+=1.0/R;}intC=indexer.size();// 将电导转换回电阻for(inti=0;i<C;i++)for(intj=0;j<C;j++)if(resistor[i][j]>EPSILON)resistor[i][j]=1.0/resistor[i][j];elseresistor[i][j]=0.0;// 构建节点电压方程组vector<vector<double>>matrix(C,vector<double>(C,0.0));vector<double>voltage(C,0.0);// 设置边界条件：起点电压 1000，终点电压 0intidxA=indexer[A],idxB=indexer[B];voltage[idxA]=1000.0;voltage[idxB]=0.0;// 起点和终点的方程简化为 V = 已知值matrix[idxA][idxA]=matrix[idxB][idxB]=1.0;// 为其他节点建立 KCL 方程for(intnode=0;node<C;node++){if(node==idxA||node==idxB)continue;for(intother=0;other<C;other++){if(resistor[node][other]>EPSILON){doubleconductance=1.0/resistor[node][other];matrix[node][other]+=conductance;matrix[node][node]-=conductance;}}}// 求解节点电压gaussianElimination(matrix,voltage);// 计算从终点 B 流出的总电流doublecurrent=0.0;for(intnode=0;node<C;node++)if(resistor[node][idxB]>EPSILON)current+=(voltage[node]-voltage[idxB])/resistor[node][idxB];// 欧姆定律计算等效电阻if(fabs(current)<EPSILON)cout<<"0.00 Ohms\n";else{cout<<fixed<<setprecision(2);cout<<(voltage[idxA]-voltage[idxB])/current;cout<<" Ohms\n";}}return0;}