POJ 3532 Resistance 题解《挑战程序设计竞赛》

POJ 3532 Resistance 

一万欧的礼物：N个节点由M条导线连接，其中连接节点X和节点Y的导线电阻为R，求整个电路的等效电阻。

4.1更加复杂的数学问题 

矩阵 

欺负我没学大学物理，根据基尔霍夫电路定律有：

设第i个节点到第j个节点在单位电势差下的电流为A_ij，设该节点的相对电势为X_i，那么除了首末节点外，各点的总电流都为0。于是得到线性方程组：

AX=B，其中B=[1, 0, 0, …, 1]^T，首末节点分别流出1单位电流，取1可以将单位限定为1欧姆。

剩下的问题就是如何求系数电流A_ij了，不考虑其他节点的影响，从节点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//////////////////////////////////

Reference

https://github.com/osak/Contest/blob/master/POJ/3532.cc

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3532 Resistance 题解《挑战程序设计竞赛》