POJ-3532 : Resistance

問題概要

ノード数N(<100)の重み付き無向グラフが与えられる。各重みを抵抗だと思ったときに1とNの間の抵抗がいくつになるか求める問題。

解法

物理の問題。ノード1の電位を1、ノードN-1の電圧を0に固定する。このとき、各頂点の電位を変数にとると、ノード1と連結なノード2~N-2の間でキルヒホッフの第一法則が成り立つのでこれで連立一次方程式を立てることができる。これを解けばノード1に流れる電流が分かるので抵抗を求めることができる。

acceptされたコード

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const double EPS = 1e-12;

double solve() {
	int N, M;
	UnionFind uf;

	scanf("%d%d", &N, &M);
	uf.init(N);
	vector< vector<double> > A(N, vector<double>(N, 0.0)), R(N, vector<double>(N, 0.0));
	vector<double> b(N, 0.0);
	b[0] = 1.0;
	for (int _ = 0; _ < M; ++_) {
		int x, y, r;
		scanf("%d%d%d", &x, &y, &r);
		--x; --y;
		if (x > y) {
			swap(x, y);
		}
		uf.merge(x, y);
		R[x][y] += 1.0 / r;
		R[y][x] += 1.0 / r;
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) if (R[i][j] > 0) {
			R[i][j] = 1.0 / R[i][j];
		}
	}

	for (int i = 0; i < N; ++i) {
		if (i != 0 && i != N - 1 && uf.isSame(0, i)) {
			for (int j = 0; j < N; ++j) if (R[i][j] > 0) {
				A[i][j] += 1.0/R[i][j];
				A[i][i] -= 1.0/R[i][j];
			}
		}
		else {
			A[i][i] = 1.0;
		}
	}

	vector<double> x = solveLinearEquations(A, b);
	double ans = 0.0;
	for (int i = 0; i < N; ++i) if (R[0][i] > 0) {
		ans += (1.0 - x[i]) / R[0][i];
	}
	return 1.0 / ans;
}