Submission #4191

# Submission time Handle Problem Language Result Execution time Memory
4191 2013-09-03T17:16:42 Z cki86201 Following Flow (kriii1_F) C++
0 / 1
0 ms 1100 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -