题目描述电阻器是电子电路中的常见元件。每个电阻器有两个端子当电流流过电阻器时部分电流转化为热量从而“抵抗”电流的流动。电阻器对电流的抵抗程度用一个正数值表示称为电阻值单位是欧姆Ohms\texttt{Ohms}Ohms。当两个电阻器串联时等效电阻等于各电阻值之和。当两个电阻器并联时等效电阻的倒数等于各电阻倒数之和。在本题中给定一个电阻网络由若干电阻器及其连接点组成需要计算两个指定点之间的等效电阻。输入格式输入包含多个测试用例。每个测试用例以一行三个整数NNN、AAA、BBB开始NNN电阻器数量不超过303030AAA、BBB需要计算等效电阻的两个端点标签接下来NNN行每行包含两个整数连接点标签和一个实数电阻值。输入以NAB0N A B 0NAB0结束。输出格式对于每个测试用例输出一行包含用例编号和等效电阻保留两位小数格式如样例所示。样例输入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−VjRij0 \sum_{j} \frac{V_i - V_j}{R_{ij}} 0j∑RijVi−Vj0其中RijR_{ij}Rij是节点iii和jjj之间的电阻如果有多个电阻并联需先合并。边界条件在本问题中设起点AAA的电压为VA1000V_A 1000VA1000任意正数设终点BBB的电压为VB0V_B 0VB0其他节点的电压为未知量求解过程建立节点电压方程组使用高斯消元法求解各节点电压计算从BBB节点流出的总电流III或流入AAA的电流等效电阻Req(VA−VB)/IR_{eq} (V_A - V_B) / IReq(VA−VB)/I解题思路步骤一离散化节点标签电阻器的连接点标签是任意正整数需要映射到0∼C−10 \sim C-10∼C−1的连续索引。mapint,intindexer;for(inti0;iN;i){cinXYR;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(inti0;iC;i)for(intj0;jC;j)if(resistor[i][j]0)resistor[i][j]1.0/resistor[i][j];步骤三建立节点电压方程对于每个节点除AAA和BBB外根据KCL\texttt{KCL}KCL建立方程∑jVi−VjRij0 \sum_{j} \frac{V_i - V_j}{R_{ij}} 0j∑RijVi−Vj0整理得(∑j1Rij)Vi−∑j1RijVj0 \left(\sum_{j} \frac{1}{R_{ij}}\right) V_i - \sum_{j} \frac{1}{R_{ij}} V_j 0(j∑Rij1)Vi−j∑Rij1Vj0在矩阵中对角线元素matrix[i][i]减去1Rij\frac{1}{R_{ij}}Rij1非对角线元素matrix[i][j]加上1Rij\frac{1}{R_{ij}}Rij1步骤四设置边界条件对于AAA和BBB节点其电压已知不需要建立KCL\texttt{KCL}KCL方程。将它们的方程设为matrix[idxA][idxA]1.0;matrix[idxB][idxB]1.0;voltage[idxA]1000.0;voltage[idxB]0.0;步骤五高斯消元求解使用列主元高斯消元法求解线性方程组AxbAx bAxb。步骤六计算总电流和等效电阻从BBB节点计算流入的总电流doublecurrent0.0;for(intnode0;nodeC;node)if(resistor[node][idxB]EPSILON)current(voltage[node]-voltage[idxB])/resistor[node][idxB];等效电阻Req(voltage[idxA]-voltage[idxB])/current;参考代码// Its Ir-Resist-Able!// UVa ID: 345// Verdict: Accepted// Submission Date: 2016-11-15// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN100;constdoubleEPSILON1e-8;// 不考虑其他连接点影响时两个连接点间的阻值doubleresistor[MAXN][MAXN];// 各个连接点的电势doublevoltage[MAXN];// 列主元高斯消元法求解线性方程组 Ax bboolgaussianElimination(vectorvectordoubleA,vectordoubleb){intnA.size();// 将 b 作为增广矩阵的最后一列for(inti0;in;i)A[i].push_back(b[i]);for(inti0;in;i){// 选取主元绝对值最大的行intpivoti;for(intji;jn;j)if(fabs(A[j][i])fabs(A[pivot][i]))pivotj;swap(A[i],A[pivot]);// 矩阵奇异if(fabs(A[i][i])EPSILON)returnfalse;// 将主元归一化for(intji1;jn;j)A[i][j]/A[i][i];// 消去其他行的当前列for(intj0;jn;j)if(i!j)for(intki1;kn;k)A[j][k]-A[j][i]*A[i][k];}// 提取解for(inti0;in;i)b[i]A[i][n];returntrue;}intmain(intargc,char*argv[]){intN,A,B,X,Y,cases0;doubleR;while(cinNAB,N0){coutCase cases: ;// 初始化电阻矩阵for(inti0;iMAXN;i)for(intj0;jMAXN;j)resistor[i][j]0.0;// 离散化节点标签mapint,intindexer;intlabel0;for(inti0;iN;i){cinXYR;if(indexer.find(X)indexer.end())indexer[X]label;if(indexer.find(Y)indexer.end())indexer[Y]label;// 合并并联电阻存储电导1/Rresistor[indexer[X]][indexer[Y]]1.0/R;resistor[indexer[Y]][indexer[X]]1.0/R;}intCindexer.size();// 将电导转换回电阻for(inti0;iC;i)for(intj0;jC;j)if(resistor[i][j]EPSILON)resistor[i][j]1.0/resistor[i][j];elseresistor[i][j]0.0;// 构建节点电压方程组vectorvectordoublematrix(C,vectordouble(C,0.0));vectordoublevoltage(C,0.0);// 设置边界条件起点电压 1000终点电压 0intidxAindexer[A],idxBindexer[B];voltage[idxA]1000.0;voltage[idxB]0.0;// 起点和终点的方程简化为 V 已知值matrix[idxA][idxA]matrix[idxB][idxB]1.0;// 为其他节点建立 KCL 方程for(intnode0;nodeC;node){if(nodeidxA||nodeidxB)continue;for(intother0;otherC;other){if(resistor[node][other]EPSILON){doubleconductance1.0/resistor[node][other];matrix[node][other]conductance;matrix[node][node]-conductance;}}}// 求解节点电压gaussianElimination(matrix,voltage);// 计算从终点 B 流出的总电流doublecurrent0.0;for(intnode0;nodeC;node)if(resistor[node][idxB]EPSILON)current(voltage[node]-voltage[idxB])/resistor[node][idxB];// 欧姆定律计算等效电阻if(fabs(current)EPSILON)cout0.00 Ohms\n;else{coutfixedsetprecision(2);cout(voltage[idxA]-voltage[idxB])/current;cout Ohms\n;}}return0;}
UVa 345 It‘s Ir-Resist-Able
发布时间：2026/5/31 20:48:29
题目描述电阻器是电子电路中的常见元件。每个电阻器有两个端子当电流流过电阻器时部分电流转化为热量从而“抵抗”电流的流动。电阻器对电流的抵抗程度用一个正数值表示称为电阻值单位是欧姆Ohms\texttt{Ohms}Ohms。当两个电阻器串联时等效电阻等于各电阻值之和。当两个电阻器并联时等效电阻的倒数等于各电阻倒数之和。在本题中给定一个电阻网络由若干电阻器及其连接点组成需要计算两个指定点之间的等效电阻。输入格式输入包含多个测试用例。每个测试用例以一行三个整数NNN、AAA、BBB开始NNN电阻器数量不超过303030AAA、BBB需要计算等效电阻的两个端点标签接下来NNN行每行包含两个整数连接点标签和一个实数电阻值。输入以NAB0N A B 0NAB0结束。输出格式对于每个测试用例输出一行包含用例编号和等效电阻保留两位小数格式如样例所示。样例输入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−VjRij0 \sum_{j} \frac{V_i - V_j}{R_{ij}} 0j∑RijVi−Vj0其中RijR_{ij}Rij是节点iii和jjj之间的电阻如果有多个电阻并联需先合并。边界条件在本问题中设起点AAA的电压为VA1000V_A 1000VA1000任意正数设终点BBB的电压为VB0V_B 0VB0其他节点的电压为未知量求解过程建立节点电压方程组使用高斯消元法求解各节点电压计算从BBB节点流出的总电流III或流入AAA的电流等效电阻Req(VA−VB)/IR_{eq} (V_A - V_B) / IReq(VA−VB)/I解题思路步骤一离散化节点标签电阻器的连接点标签是任意正整数需要映射到0∼C−10 \sim C-10∼C−1的连续索引。mapint,intindexer;for(inti0;iN;i){cinXYR;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(inti0;iC;i)for(intj0;jC;j)if(resistor[i][j]0)resistor[i][j]1.0/resistor[i][j];步骤三建立节点电压方程对于每个节点除AAA和BBB外根据KCL\texttt{KCL}KCL建立方程∑jVi−VjRij0 \sum_{j} \frac{V_i - V_j}{R_{ij}} 0j∑RijVi−Vj0整理得(∑j1Rij)Vi−∑j1RijVj0 \left(\sum_{j} \frac{1}{R_{ij}}\right) V_i - \sum_{j} \frac{1}{R_{ij}} V_j 0(j∑Rij1)Vi−j∑Rij1Vj0在矩阵中对角线元素matrix[i][i]减去1Rij\frac{1}{R_{ij}}Rij1非对角线元素matrix[i][j]加上1Rij\frac{1}{R_{ij}}Rij1步骤四设置边界条件对于AAA和BBB节点其电压已知不需要建立KCL\texttt{KCL}KCL方程。将它们的方程设为matrix[idxA][idxA]1.0;matrix[idxB][idxB]1.0;voltage[idxA]1000.0;voltage[idxB]0.0;步骤五高斯消元求解使用列主元高斯消元法求解线性方程组AxbAx bAxb。步骤六计算总电流和等效电阻从BBB节点计算流入的总电流doublecurrent0.0;for(intnode0;nodeC;node)if(resistor[node][idxB]EPSILON)current(voltage[node]-voltage[idxB])/resistor[node][idxB];等效电阻Req(voltage[idxA]-voltage[idxB])/current;参考代码// Its Ir-Resist-Able!// UVa ID: 345// Verdict: Accepted// Submission Date: 2016-11-15// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN100;constdoubleEPSILON1e-8;// 不考虑其他连接点影响时两个连接点间的阻值doubleresistor[MAXN][MAXN];// 各个连接点的电势doublevoltage[MAXN];// 列主元高斯消元法求解线性方程组 Ax bboolgaussianElimination(vectorvectordoubleA,vectordoubleb){intnA.size();// 将 b 作为增广矩阵的最后一列for(inti0;in;i)A[i].push_back(b[i]);for(inti0;in;i){// 选取主元绝对值最大的行intpivoti;for(intji;jn;j)if(fabs(A[j][i])fabs(A[pivot][i]))pivotj;swap(A[i],A[pivot]);// 矩阵奇异if(fabs(A[i][i])EPSILON)returnfalse;// 将主元归一化for(intji1;jn;j)A[i][j]/A[i][i];// 消去其他行的当前列for(intj0;jn;j)if(i!j)for(intki1;kn;k)A[j][k]-A[j][i]*A[i][k];}// 提取解for(inti0;in;i)b[i]A[i][n];returntrue;}intmain(intargc,char*argv[]){intN,A,B,X,Y,cases0;doubleR;while(cinNAB,N0){coutCase cases: ;// 初始化电阻矩阵for(inti0;iMAXN;i)for(intj0;jMAXN;j)resistor[i][j]0.0;// 离散化节点标签mapint,intindexer;intlabel0;for(inti0;iN;i){cinXYR;if(indexer.find(X)indexer.end())indexer[X]label;if(indexer.find(Y)indexer.end())indexer[Y]label;// 合并并联电阻存储电导1/Rresistor[indexer[X]][indexer[Y]]1.0/R;resistor[indexer[Y]][indexer[X]]1.0/R;}intCindexer.size();// 将电导转换回电阻for(inti0;iC;i)for(intj0;jC;j)if(resistor[i][j]EPSILON)resistor[i][j]1.0/resistor[i][j];elseresistor[i][j]0.0;// 构建节点电压方程组vectorvectordoublematrix(C,vectordouble(C,0.0));vectordoublevoltage(C,0.0);// 设置边界条件起点电压 1000终点电压 0intidxAindexer[A],idxBindexer[B];voltage[idxA]1000.0;voltage[idxB]0.0;// 起点和终点的方程简化为 V 已知值matrix[idxA][idxA]matrix[idxB][idxB]1.0;// 为其他节点建立 KCL 方程for(intnode0;nodeC;node){if(nodeidxA||nodeidxB)continue;for(intother0;otherC;other){if(resistor[node][other]EPSILON){doubleconductance1.0/resistor[node][other];matrix[node][other]conductance;matrix[node][node]-conductance;}}}// 求解节点电压gaussianElimination(matrix,voltage);// 计算从终点 B 流出的总电流doublecurrent0.0;for(intnode0;nodeC;node)if(resistor[node][idxB]EPSILON)current(voltage[node]-voltage[idxB])/resistor[node][idxB];// 欧姆定律计算等效电阻if(fabs(current)EPSILON)cout0.00 Ohms\n;else{coutfixedsetprecision(2);cout(voltage[idxA]-voltage[idxB])/current;cout Ohms\n;}}return0;}
