Submission #4191

#	Time	Username	Problem	Language	Result	Execution time	Memory
4191		cki86201	Following Flow (kriii1_F)	C++98	0 / 1	0 ms	1100 KiB

F

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;

const double EPS = 1e-8;
double mat[32][32];
int N,M;
int out[32];
int cnt[32][32];
double val[32];
double ed[32];

inline double ab(double x){return x>0?x:-x;}

void gauss(int x,int y,double t)
{
	int i;
	for(i=0;i<N;i++){
		double tmp=t*mat[y][i];
		mat[x][i]-=tmp;
	}
	val[x]-=t*val[y];
}

void solve()
{
	int i,j;
	for(i=0;i<N;i++){
		for(j=i+1;j<N;j++){
			if(ab(mat[j][i])<EPS)continue;
			gauss(j,i,mat[j][i]/mat[i][i]);
		}
	}
	for(i=N-1;i>=0;i--){
		ed[i]=val[i];
		for(j=i+1;j<N;j++){
			ed[i]-=mat[i][j]*ed[j];
		}
		ed[i]/=mat[i][i];
	}
	printf("%.10f",ed[0]);
}

int main()
{
	scanf("%d%d",&N,&M);
	int i,j;
	for(i=1;i<=M;i++){
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		if(y!=N)mat[x][y]-=1.0;
		out[x]++;
		val[x]+=t;
	}
	for(i=0;i<N;i++){mat[i][i]=1.0;val[i]/=(double)out[i];}
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			if(i!=j)mat[i][j]/=(double)out[i];
		}
	}
	solve();
	return 0;
}

• Subtask 1: 0 / 1