Cod sursa(job #801658)

Utilizator ChallengeMurtaza Alexandru Challenge Data 24 octombrie 2012 19:12:34
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
/*
	PROB: tunel
	LANG: C++
*/

#include <fstream>
#include <iostream>
#include <iomanip>

#define DEBUG

#ifndef DEBUG
	#define PRINT(x)
	#define D if(0)
#else
	#define PRINT(x) \
		cout<<#x<<":\t"<<x<<endl
	#define D if(1)
#endif

using namespace std;

const char InFile[]="tunel.in";
const char OutFile[]="tunel.out";
const int MaxN=260;
const long double EPS=1e-5;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,x,y,c,deg[MaxN];
long double A[MaxN][MaxN],SOL[MaxN];

inline double myabs(const double &x)
{
	if(x<0)
	{
		return -x;
	}
	return x;
}

inline bool isZero(const double &x)
{
	return myabs(x)<EPS;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y>>c;
		++deg[x];
		++deg[y];
		++A[x][y];
		++A[y][x];
		A[x][N+1]-=c;
		A[y][N+1]-=c;
	}
	fin.close();
	
	for(register int i=1;i<=N-1;++i)
	{
		if(deg[i])
		{
			for(register int j=1;j<=N+1;++j)
			{
				A[i][j]/=deg[i];
			}
			A[i][i]=-1.0;
		}
	}
	for(register int j=1;j<=N+1;++j)
	{
		A[N][j]=0.0;
	}

	int i=1,j=1;
	while(i<=N && j<=N)
	{
		int k=i;
		for(;k<=N;++k)
		{
			if(!isZero(A[k][j]))
			{
				break;
			}
		}

		if(k==N+1)
		{
			++j;
			continue;
		}

		if(i!=k)
		{
			for(register int c=1;c<=N+1;++c)
			{
				swap(A[i][c],A[k][c]);
			}
		}

		for(register int c=j+1;c<=N+1;++c)
		{
			A[i][c]/=A[i][j];
		}
		A[i][j]=1.0;

		for(register int l=i+1;l<=N;++l)
		{
			for(register int c=j+1;c<=N+1;++c)
			{
				A[l][c]-=A[l][j]*A[i][c];
			}
			A[l][j]=0.0;
		}

		++i;
		++j;
	}

	for(register int i=N;i>0;--i)
	{
		for(register int j=1;j<=N;++j)
		{
			if(!isZero(A[i][j]))
			{
				SOL[j]=A[i][N+1];
				for(register int k=j+1;k<=N;++k)
				{
					SOL[j]-=SOL[k]*A[i][k];
				}
				break;
			}
		}
	}
	
	fout<<fixed<<setprecision(5);
	fout<<SOL[1];
	fout.close();
	return 0;
}