一万欧的礼物:N个节点由M条导线连接,其中连接节点X和节点Y的导线电阻为R,求整个电路的等效电阻。
4.1更加复杂的数学问题
矩阵
欺负我没学大学物理,根据基尔霍夫电路定律有:
设第i个节点到第j个节点在单位电势差下的电流为Aij,设该节点的相对电势为Xi,那么除了首末节点外,各点的总电流都为0。于是得到线性方程组:
AX=B,其中B=[1, 0, 0, …, 1]T,首末节点分别流出1单位电流,取1可以将单位限定为1欧姆。
剩下的问题就是如何求系数电流Aij了,不考虑其他节点的影响,从节点x到节点y的电阻仅仅由两者之间并联的导线电阻决定,而此时电势为1单位,那么电流就知道了,只要分别遍历一遍与该节点连接的节点,就能算出来代数和了。
之后就是高斯消元法了,求出了各点电势后,计算起点一共流出了多少电流,用单位电势除以这个电流,就得出了等效电阻。
#include <iostream> #include <vector> using namespace std; #define MAX_N 100 double resistor[MAX_N][MAX_N]; // 不考虑其他节点影响时,两个节点间的电阻 double voltage[MAX_N]; // 两个节点间的电势 // 高斯消元法求解线性方程组 ax = b ,a是系数矩阵,N个方程,M个未知数,b为解向量,返回false表示误解 // N < M 的时候必须填充 0 = 0 使得 N == M 。 // O(M^2 N) template <class T> bool gaussian_elimination(vector<vector<T> >& a, vector<T>& b) { const int N = a.size(); const int M = a[0].size(); // assert(N >= M) for (int i = 0, p = 0; i < M; i++, p++) { int q; for (q = p; q < N && a[q][i] == 0; q++); if (q == N) { --p; continue; } swap(a[i], a[q]); swap(b[i], b[q]); const T r = 1.0 / a[i][i]; for (int k = i; k < M; k++) { a[i][k] = a[i][k] * r; } b[i] = b[i] * r; for (int j = 0; j < N; j++) { if (j == i) continue; const T t = a[j][i]; for (int k = i; k < M; k++) { a[j][k] = a[j][k] - t * a[i][k]; } b[j] = b[j] - t * b[i]; } } for (int i = 0; i < M; i++) { if (a[i][i] == 0 && b[i] != 0) return false; // 无解 } return true; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int N, M; while (~scanf("%d%d", &N, &M)) { memset(resistor, 0, sizeof(resistor)); for (int i = 0; i < M; ++i) { int X, Y, R; scanf("%d%d%d", &X, &Y, &R); resistor[X - 1][Y - 1] += 1.0 / R; resistor[Y - 1][X - 1] += 1.0 / R; } for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { resistor[i][j] = 1.0 / resistor[i][j]; // 并联后的电阻 } } vector<vector<double> > matrix(N, vector<double>(N, 0)); vector<double> voltage(N, 0); voltage[0] = 1.0; // 节点电势,取起点为单位电势,终点为0电势 voltage[N - 1] = 0.0; matrix[0][0] = matrix[N - 1][N - 1] = 1; // 系数表示单位电势下两个节点间的电流,那么真实电势则为未知数 for (int node = 1; node < N - 1; ++node) { for (int other = 0; other < N; ++other) { if (resistor[node][other] > 0) { double inv = 1.0 / resistor[node][other]; // 单位电势下从node流到other的电流 // 基尔霍夫电流定律:所有进入某节点的电流的总和等于所有离开这节点的电流的总和 matrix[node][node] -= inv; // node处流走了这么多 matrix[node][other] += inv; // other处流入了这么多 } } } gaussian_elimination(matrix, voltage); // 求解各节点的电势 double current = 0; for (int node = 0; node < N; ++node) { if (resistor[0][node] > 0) { current += (voltage[0] - voltage[node]) / resistor[0][node]; // 从起点到终点单位电势下的电流之和 } } printf("%.2f\n", 1.0 / current); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
14381170 | hankcs | 3532 | Accepted | 272K | 0MS | C++ | 2710B | 2015-07-12 21:23:14 |
Reference
https://github.com/osak/Contest/blob/master/POJ/3532.cc