Submission #19522

#	Time	Username	Problem	Language	Result	Execution time	Memory
19522		gs14004	Following Flow (kriii1_F)	C++14	1 / 1	0 ms	1732 KiB

F

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <assert.h>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, m;
double arr[33][33];

vector<double> gauss_jordan(vector<double> &x){ // solve Ax = B. 
	for(int i=0; i<n; i++) arr[i][n] = x[i];
	for(int i=0; i<n; i++){
		int piv = i;
		for(int j=i; j<n; j++){
			if(fabs(arr[j][i]) > fabs(arr[piv][i])){
				piv = j;
			}
		}
		swap(x[i], x[piv]);
		if(fabs(arr[i][i]) < 1e-8){
			while(1);
		}
		for(int j=i+1; j<=n; j++){
			arr[i][j] = (arr[i][j] / arr[i][i]);
		}
		for(int j=0; j<n; j++){
			if(i != j){
				for(int k=i+1; k<=n; k++){
					arr[j][k] -= arr[j][i] * arr[i][k];
				}
			}
		}
	}
	vector<double> ret;
	for(int i=0; i<n; i++) ret.push_back(arr[i][n]);
	return ret;
}

vector<pi> gph[33];
int deg[33];

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		if(s == n) continue;
		gph[s].push_back(pi(x, e));
		deg[s]++;
	}
	vector<double> b(n+1);
	for(int i=0; i<n; i++){
		arr[i][i] += 1;
		// t(i) = (t(j) + d(j, i)) / deg(j)
		for(auto &j : gph[i]){
			arr[i][j.second] -= 1.0 / deg[i];
			b[i] += 1.0 * j.first / deg[i];
		}
	}
	arr[n][n] = 1;
	n++;
	printf("%.10f",gauss_jordan(b)[0]);
}

• Subtask 1: 1 / 1