Cod sursa(job #319699)

Utilizator andrei.12Andrei Parvu andrei.12 Data 1 iunie 2009 20:03:54
Problema Tunelul groazei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>

using namespace std;

#define lg 260
#define eps 0.00001
#define a A

int n, m, x, y, z, i, j, k;
double A[lg][lg], aux;

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

int main()
{
	freopen("tunel.in", "rt", stdin);
	freopen("tunel.out", "wt", stdout);

	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 ++){
		for (j = 1; j <= n+1; j ++)
			printf("%lf ", A[i][j]);
		printf("\n");
	}
	*/

	for (i = 1; i <= n; i ++){
		if (ab(A[i][i]) < eps)
			for (j = i; j <= n; j ++)
				if (ab(A[j][i]) > eps)
					for (k = 1; k <= n+1; k ++)
						swap(A[i][k], A[j][k]);

		if (!A[i][i])
			break;

		aux = 1/A[i][i];
		for (j = 1; j <= n+1; j ++)
			A[i][j] *= aux;
		for (j = 1; j <= n; j ++)
			if (i != j){
				aux = A[j][i];
				for (k = i; k <= n+1; k ++)
					A[j][k] -= aux * A[i][k];
			}
	}

	/*for (i = 1; i <= n; i ++){
		for (j = 1; j <= n+1; j ++)
			printf("%lf ", A[i][j]);
		printf("\n");
	}
	*/

	printf("%.3lf\n", A[1][n+1] / A[1][1]);

	return 0;
}