Cod sursa(job #793941)

Utilizator danalex97Dan H Alexandru danalex97 Data 4 octombrie 2012 19:59:46
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <iomanip>
using namespace std;

const int Nmax = 265;
double EPS=0.0000001;

int N,M;
double A[Nmax][Nmax];
double X[Nmax];
int Grad[Nmax];

ifstream F("tunel.in");
ofstream G("tunel.out");

int main()
{
    F>>N>>M;
    for (int i=1,x,y,c;i<=M;++i)
    {
        F>>x>>y>>c;
        ++Grad[x], ++Grad[y];
        ++A[x][y], ++A[y][x];
        A[x][N+1] -= c, A[y][N+1] -= c;
    }
    for (int i=1;i<=N;++i)
	{
		for(int j=1;j<=N+1;++j)
			A[i][j]/=(double)Grad[i];
		A[i][i]=-1.0;
	}
	for(int i=1;i<=N+1;++i)
		A[N][i]=0.0;

    for (int i=1,j=1,k;i<=N && j<=N;++i,++j)
    {
        for ( k=i;k<=N;++k )
            if ( A[k][j]<-EPS || A[k][j]>EPS )
                break;
        if ( k==N+1 )
        {
            --i;
            continue;
        }

        if ( i != k )
            for (int l=1;l<=N+1;++l)
                swap(A[i][l],A[k][l]);

        for (int l=j+1;l<=N+1;++l)
            A[i][l] /= A[i][j];
        A[i][j]=1.0;

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

    for (int i=N-1;i;--i)
	{
		bool Ok=0;
		for (int j=1;j<=N+1 && !Ok;++j)
			if ( A[i][j]>EPS || A[i][j]<-EPS )
			{
				Ok=1, X[j]=A[i][N+1];
				for (int k=j+1;k<=N;k++)
					X[j]-=X[k]*A[i][k];
			}
	}

	G<<fixed<<setprecision(8)<<X[1]<<'\n';

    F.close();
    G.close();
    return 0;
}