Submission #3674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3674	2013-08-31T07:36:01 Z	wookayin	Following Flow (kriii1_F)	C++	1 / 1	0 ms	1680 KB

F

#include <utility>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <cstdio>

using namespace std;
#pragma warning(disable:4996)

#define REP(t, n) for(int t=0; t<(int)(n); ++t)
#define FOR(t, x, y) for(int t=x; t<(int)(y); ++t)

int n, m;
vector< pair<int,int> > gr[33];

vector< vector<double> > A;
vector< double > B;

void gauss(vector< vector<double> > &A, vector<double> &b, vector<double> & x)
{
	int n = A.size();
	const double EPS = 1e-9;

	REP(i, n) {
		int pivot = i;
		for(int j = i+1; j<n; ++j)
			if( fabs(A[j][i]) > fabs(A[pivot][i]) ) pivot = j;

		A[pivot].swap(A[i]);
		swap(b[pivot], b[i]);

		if(-EPS <= A[i][i] && A[i][i] <= EPS)
			throw "wtf";
		
		for(int j = i +1; j < n; ++ j) {
			b[j] -= A[j][i] * b[i] / A[i][i];
			for(int k = n-1; k >= i; -- k)
				A[j][k] -= A[i][k] * A[j][i] / A[i][i];
		}
	}

	x.resize(n);
	x[n-1] = b[n-1] / A[n-1][n-1];
	for(int i = n-2; i >= 0; -- i) {
		double t = b[i];
		for(int j = i + 1; j < n; ++ j)
			t -= A[i][j] * x[j];
		x[i] = t / A[i][i];
	}

}

double linear() {
	B.resize(n);
	A.resize(n, vector<double>(n));

	REP(x, n) {
		// p(x->y)
		REP(j, gr[x].size()) {
			int y = gr[x][j].first;
			int time = gr[x][j].second;

			double pxy = 1.0 / gr[x].size();

			// 상수항
			B[x] -= time * pxy;
			// 팩터
			A[x][y] += pxy;
		}
		A[x][x] += -1.0;
	}
	
	/*
	REP(x, n) {
		REP(y, n) cout << setprecision(4) << A[x][y] << '\t';
		cout << " : " << B[x] << endl;
	}
	*/

	vector<double> x;
	gauss(A, B, x);

	/*
	REP(i, n) {
		cout << "x" << i << " = " << x[i] << endl;
	}
	*/
	return x[0];
}

int main() {
	cin >> n >> m;
	n ++;
	for(int j =0 ; j < m; ++ j) {
		int x,y,p;
		cin >> x >> y >> p;
		gr[x].push_back( make_pair(y, p) );
	}

	cout << setprecision(14) << linear() << endl;

	return 0;
}

Subtask #1

1.0 / 1.0

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