Submission #4493

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4493	2013-10-12T02:49:49 Z	jays	Following Flow (kriii1_F)	C++	1 / 1	0 ms	1672 KB

F

#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const double EPS = 1e-9;

int N, M;
vector<int> adj[32], weight[32];

double solve(double* out) {
	double A[32][32] = {0.0, }, B[32] = {0,0, };
	for (int u = 0; u < N; ++u) {
		A[u][u] = 1.0;
		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i];
			int w = weight[u][i];
			A[u][v] += -1.0/out[u];
			B[u] += 1.0*w/out[u];
		}
	}
	// Gauss Elimination
	for (int i = 0; i < N; ++i) {
		// Find Max Coefficient Row
		double mx = 0.0;
		int index = -1;
		for (int j = i; j < N; ++j) {
			if (abs(A[j][i] > mx)) {
				mx = abs(A[j][i]);
				index = j;
			}
		}
		// Swapping
		for (int j = 0; j < N; ++j)
			swap(A[i][j], A[index][j]);
		swap(B[i], B[index]);
		// Target Variable's Coefficient to 1
		double coefficent = A[i][i];
		for (int j = 0; j < N; ++j)
			A[i][j] /= coefficent;
		B[i] /= coefficent;
		// Remove A Variable and Recalculate Matrix
		for (int j = 0; j < N; ++j) {
			if (j != i && abs(A[j][i]) > EPS) {
				double temp = A[j][i];
				for (int k = 0; k < N; ++k)
					A[j][k] -= temp * A[i][k];
				B[j] -= temp * B[i];
			}
		}
	}
	return B[0];
}

int main() {
	double out[32] = {0.0, };
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back(v);
		weight[u].push_back(w);
		out[u]++;
	}
	printf("%.10lf\n", solve(out));
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1672 KB	Output is correct
2	Correct	0 ms	1672 KB	Output is correct
3	Correct	0 ms	1672 KB	Output is correct
4	Correct	0 ms	1672 KB	Output is correct
5	Correct	0 ms	1672 KB	Output is correct
6	Correct	0 ms	1672 KB	Output is correct
7	Correct	0 ms	1672 KB	Output is correct
8	Correct	0 ms	1672 KB	Output is correct
9	Correct	0 ms	1672 KB	Output is correct
10	Correct	0 ms	1672 KB	Output is correct
11	Correct	0 ms	1672 KB	Output is correct
12	Correct	0 ms	1672 KB	Output is correct
13	Correct	0 ms	1672 KB	Output is correct
14	Correct	0 ms	1672 KB	Output is correct
15	Correct	0 ms	1672 KB	Output is correct