Submission #4185

#	Time	Username	Problem	Language	Result	Execution time	Memory
4185		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 edge[32][32];
int out[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++)mat[x][i]-=t*mat[y][i];
	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[i][j])<EPS)continue;
			gauss(j,i,mat[j][i]/mat[j-1][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()
{
	//freopen("input.txt","r",stdin);
	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(!edge[x][y])out[x]++;
		edge[x][y]+=t;
		val[x]+=t;
	}
	for(i=0;i<N;i++){mat[i][i]=1;val[i]/=(double)out[i];}
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			if(edge[i][j])mat[i][j]=-1.0/out[i];
		}
	}
	solve();
	return 0;
}

• Subtask 1: 0 / 1