n个结点, m个纯电阻, 求1号点到n号点的等效电阻, 精确到小数点后两位. 多组数据. 虽然题面没说, 但n≤100, m可能很大. 虽然题面说了, 但数据中不存在电阻为0的情形. 物理背景 欧姆定律: 纯电阻电路中, 流经电阻的电流等于电阻两端的电压与电阻阻值之比. 电势与电压:
以为n, m都会很小, 一开始我的方程组是这样的: n个结点的电势和流经m个电阻的电流, 并另设一个总电流作未知数. 对每个电阻根据欧姆定律列方程, 前(n-1)个结点根据基尔霍夫电流定律列方程, 然后令1号结点为零势面, 1号结点和n号结点之间接一个1kV的理想恒压电源. 这样共有(n+m+1)个未知数和(n+m+1)条方程, 短接的情况也能正常处理.
然后TLE了......
参考了一下题解, 发现m可能很大, 因此要把电流用电势差和电阻表示, 手动代入基尔霍夫定律的方程. 这样无法直接处理短接的情况, 但本题实际上不存在R=0的数据. 如果需要处理, 用并查集合并短接的两端即可.
现在方程组是这样: n个结点的电势作未知数. 前(n-1)个结点用欧姆定律表示出电流, 根据基尔霍夫电流定律列方程; 令1号结点为零势面, 在1号结点和n号结点之间接一个1A的理想恒流电源.
流出n号结点的电流必然等于流入1号结点的电流, 这条方程是多余的.
本文叙述不妥之处恳请指出.
const int N = 100;
const double eps = 1e-9;
double a[N][N+1];
void gauss(int n)
{
Rep (i, 0, n) {
int r = i;
Rep (j, i+1, n) if (fabs(a[j][i]) > fabs(a[r][i])) r = j;
if (fabs(a[r][i]) < eps) continue;
if (r != i) For (j, 0, n) swap(a[i][j], a[r][j]);
Rep (j, i+1, n)
Down (k, n, i)
a[j][k] -= a[i][k] * a[j][i] / a[i][i];
}
}
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) == 2) {
Rep (i, 0, n)
fill_n(a[i], n+1, 0);
a[0][0] = 1;
Rep (i, 0, m) {
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
--x, --y;
if (x == y) continue;
if (x > y) swap(x, y);
double g = 1.0/r;
a[x+1][y] += g;
a[x+1][x] -= g;
if (y != n-1) {
a[y+1][x] += g;
a[y+1][y] -= g;
}
}
a[1][n] = 1;
gauss(n);
printf("%.2f\n", a[n-1][n] / a[n-1][n-1]);
}
return 0;
}