Cod sursa(job #485852)

Utilizator ilincaSorescu Ilinca ilinca Data 19 septembrie 2010 18:46:36
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <cstring>

#define nmax 260
#define eps 0.0000001

int n;
double a [nmax] [nmax];


void print ()
{
	int i, j;
	for (i=1; i <= n; ++i)
	{
		for (j=1; j <= n+1; ++j)
			fprintf (stderr, "%lf ", a [i] [j]);
		fprintf (stderr, "\n");
	}
	fprintf (stderr, "\n");
}

inline void swap (double a, double b)
{double aux; aux=a; a=b; b=aux;}

inline double fabs (double a)
{return (a<0)? -a:a;}

void gauss ()
{
	int i, j, k;
	double w;
	for (i=1; i <= n; ++i)
	{
		for (j=i; j <= n && fabs (a [j] [i]) < eps; ++j);
		if (fabs (a [j] [i]) < eps || j > n) break;
		if (j != i) for (k=1; k <= n+1; ++k) swap (a [i] [k], a [j] [k]);
		w=1.0/a [i] [i];
		for (j=1; j <= n+1; ++j) a [i] [j] *= w;
		for (j=1; j <= n; ++j)
			if (i != j)
			{
				w=a [j] [i]/a [i] [i];
				for (k=i; k <= n+1; ++k) a [j] [k]-=w*a [i] [k];
			}	
	}
}

int main ()
{
	freopen ("tunel.in", "r", stdin);
	freopen ("tunel.out", "w", stdout);
	int i, j, m, x, y, z;
	double aux;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d%d", &x, &y, &z);
		++a [x] [x]; ++a [y] [y];
		++a [x] [y]; ++a [y] [x];
		a [x] [n+1] += z;
		a [y] [n+1] += z;
	}
	for (i=1; i <= n; ++i)
	{
		aux=1.0/a [i] [i];
		for (j=1; j <= n+1; ++j) a [i] [j] *= aux;
		a [i] [i]=-1;
	}
	memset (a [n], 0, sizeof (a [n]));
	a [n] [1]=1;
	//print ();
	gauss ();
	//print ();
	printf ("%.3lf\n", a [n] [n+1]/a [n] [n]);
	return 0;
}