| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 3673 | wookayin | Following Flow (kriii1_F) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <utility>
#include <vector>
#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;
}