BZOJ2419 电阻

记得这是高一的时候ty同学和我说的东西了。然后现在才解决，可以打败上帝造题的七分钟，荣登解决时间最长的题目了。

其实也就是一个高斯消元，用电势来列方程。不过高斯消元写得不熟，平时有空都写ds的题去了。以后不能再这样了。

用自己的代码高亮脚本了，虽然还不完善不过还是很开心的。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int maxn = 109;
const double inf = 1e100;
const double eps = 1e-8;

double x[maxn], a[maxn][maxn], b[maxn][maxn];
int n, m, perm[maxn];

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	srand(19970911);
	while (scanf("%d%d", &n, &m) != EOF) {
		for (int i = 1; i <= n; ++ i)
			perm[i] = i;
		if (n > 2)
			random_shuffle(perm + 2, perm + n);
		for (int i = 1; i <= n; ++ i)
			for (int j = 1; j <= n; ++ j)
				if (i == j)
					a[i][j] = 0;
				else
					a[i][j] = inf;
		while (m --) {
			int u, v;
			double p;
			scanf("%d%d%lf", &u, &v, &p);
			u = perm[u];
			v = perm[v];
			if (u == v)
				continue;
			a[u][v] = 1.0 / (1.0 / a[u][v] + 1.0 / p);
			a[v][u] = a[u][v];
		}
		b[1][1] = 1;
		for (int i = 2; i <= n; ++ i)
			b[1][i] = 0;
		b[1][n + 1] = 0;
		for (int i = 2; i <= n; ++ i) {
			double sr(0);
			for (int j = 1; j <= n; ++ j)
				if (i != j)
					sr += 1.0 / a[i][j];
			for (int j = 1; j <= n; ++ j)
				if (i == j)
					b[i][j] = - sr;
				else
					b[i][j] = 1.0 / a[i][j];
			if (i == n)
				b[i][n + 1] = -1;
			else
				b[i][n + 1] = 0;
		}
		for (int i = 1; i <= n; ++ i) {
			int j0(i);
			for (int j = i + 1; j <= n; ++ j)
				if (abs(b[j0][i]) < abs(b[j][i]))
					j0 = j;
			if (j0 ^ i)
				for (int j = 1; j <= n + 1; ++ j)
					swap(b[i][j], b[j0][j]);
			for (int j = i + 1; j <= n; ++ j) {
				double rat(b[j][i] / b[i][i]);
				for (int k = 1; k <= n + 1; ++ k)
					b[j][k] -= b[i][k] * rat;
			}
		}
		printf("%.2lf\n", b[n][n + 1] / b[n][n]);
	}
}