Cod sursa(job #801982)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 25 octombrie 2012 16:38:27
Problema Tunelul groazei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;

const int N = 260;
const int M = 110000;

const double eps = 0.0001;

int n, m, gr[N], a[M], b[M], c[M];
double e[N][N], x[N];

inline double mabs(double x) {return x > 0 ? x : -x;}
inline bool ver(double x) {
	return mabs(x) > eps;
}

void gauss() {
	int i = 1, j = 1, k, u, l;
	
	while(i <= n && j <= n + 1) {
		
		for(k = i; k<n; ++k)
			if(ver(e[k][j]))
				break;
		
		if(k != i)
			for(u = 1; u<=n + 1; ++u)
				swap(e[i][u], e[k][u]);
		
		for(u = j + 1; u<=n + 1; ++u)
			e[i][u] /= e[i][j];
		e[i][j] = 1;
		
		for(u = i + 1; u<n; ++u) {
			
			for(l = j + 1; l<=n + 1; ++l)
				e[u][l] -= e[u][j]*e[i][l];
			e[u][j] = 0;
		}
		
		++i; ++j;
	}
	
	for(i = n - 1; i; --i)
		for(j = 1; j<=n + 1; ++j) if(ver(e[i][j])) {
			
			if(j == n + 1) {
				cout << "No solution";
				return;
			}
			
			x[j] = e[i][n + 1];
			for(l = j + 1; j<n; ++j)
				x[j] -= e[i][l] * x[l];
			break;
		}
}

int main() {
	int i;
	freopen("tunel.in", "r", stdin);
	freopen("tunel.out", "w", stdout);
	
	cin >> n >> m;
	
	for(i = 1; i<=m; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		
		gr[a[i]]++;
		gr[b[i]]++;
	}
	
	for(i = 1; i<=m; ++i) {
		
		e[a[i]][b[i]] += (double)1/gr[a[i]];
		e[b[i]][a[i]] += (double)1/gr[b[i]];
		
		e[a[i]][n + 1] -= (double)c[i]/gr[a[i]];
		e[b[i]][n + 1] -= (double)c[i]/gr[b[i]];
	}
	
	for(i = 1; i<=n; ++i) {
		e[i][i] = -1;
		e[i][n] = 0;
	}
	
	gauss();
	
	cout << setprecision(4) << fixed << x[1];
	
	return 0;
}