Cod sursa(job #362696)

Utilizator katakunaCazacu Alexandru katakuna Data 10 noiembrie 2009 18:36:00
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 260
int n, m, i, j, a, b, c, k;
int grad[Nmax];
double cc, vaux;
double D[Nmax], G[Nmax][Nmax], X[Nmax], aux[Nmax];

void citire () {
	
	FILE *f = fopen ("tunel.in", "r");	
	fscanf (f, "%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		fscanf (f, "%d %d %d", &a, &b, &c);
		G[a][b]--; G[b][a]--; G[a][a]++; G[b][b]++;
		D[a]+= c; D[b]+=c;
	}
	
	fclose (f);
}

void solve () {
	
	for (i = 1; i < n; i++) {
		
		for (j = i+1; j < n; j++) {	
			if (G[j][i] ) { 
				cc = G[j][i] / G[i][i];
				for (k = i; k < n; k++) {
					G[j][k]-= cc * G[i][k];
				}
				
				D[j]-=  cc * D[i]; 
			}
		}
	}
	
	X[n-1] = D[n-1] / G[n-1][n-1];
	for (i = n-2; i >= 1; i--) {
		cc = 0;
		for (j = i + 1; j < n; j++)
			cc+= G[i][j] * X[j];
		
		X[i] = (D[i] - cc) / G[i][i];
	}
	
}

int main () {
	
	citire ();
	solve ();
	
	FILE *g = fopen ("tunel.out", "w");
	fprintf (g, "%lf", X[1]);
	fclose (g);
	
	return 0;
}