Cod sursa(job #126721)

Utilizator snaked31Stanica Andrei snaked31 Data 22 ianuarie 2008 18:47:53
Problema Tunelul groazei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define nm 256

int n, m, a, b, c, i;
double C[nm][nm];
double g[nm];
double sol;


void read()

{
	scanf("%d %d ", &n, &m);
	for (i=1; i<=m; ++i)
	{
		scanf("%d %d %d ", &a, &b, &c);

		//v[a].pb(b);
		//v[b].pb(a);
		//C[a].pb(c);
		//C[b].pb(c);
		++ g[a];
		++ g[b];
		-- C[a][b];
		-- C[b][a];
		C[a][n+1] += c;
		C[b][n+1] += c;
	}
}


void gauss()

{
	int i, j, k;

	for (i=1; i<=n; ++i)
	{
		for (j=i; C[i][j] == 0; ++j);
		if (j != i)
		{
			for (k=1; k<=n+1; ++k)
				swap(C[i][k], C[j][k]);
		}
		for (j=1; j<=n; ++j)
		{
			if (j != i)
			{
				double ratio = C[j][i] / C[i][i];
				
				for (k=1; k<=n+1; ++k)
				{
					C[j][k] -= (C[i][k] * ratio);
				}
			}
		}
	}
}


void solve()

{
	for (i=1; i<=n; ++i)
	{
		C[i][i] = g[i];
	}
	gauss();
	sol = C[1][n+1] / C[1][1];
	printf("%lf %lf\n", C[1][n+1] , C[1][1]);
}


void write()

{
	printf("%lf\n", sol);
}


int main()

{
	freopen("tunel.in", "r", stdin);
	freopen("tunel.out","w",stdout);

	read();
	solve();
	write();

	return 0;
}