Cod sursa(job #1786652)

Utilizator Athena99Anghel Anca Athena99 Data 23 octombrie 2016 14:06:14
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <algorithm>
#include <fstream>
#include <iomanip>

using namespace std;

ifstream fin("tunel.in");
ofstream fout("tunel.out");

const int nmax= 255;
const int out_precision= 3;

double a[nmax+1][nmax+2];

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1; i<=m; ++i ) {
        int x, y, z;
        fin>>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 ( int i= 1; i<=n+1; ++i ) {
        a[n][i]= 0;
    }
    a[n][n]= 1;

    for ( int i= 1, j= 1, k; i<=n && j<=n; ++i, ++j ) {
        for ( k= i; k<=n && a[k][j]==0; ++k ) ;
        if ( k<=n ) {
            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][l]/a[i][j];
            }
            a[i][j]= 1;

            for ( int l= i+1; l<=n; ++l ) {
                for ( int o= j+1; o<=n+1; ++o ) {
                    a[l][o]= a[l][o]-a[l][j]*a[i][o];
                }
                a[l][j]= 0;
            }
        } else {
            --i;
        }
    }

    for ( int i= n; i>=1; --i ) {
        for ( int j= i-1; j>=1; --j ) {
            a[j][n+1]= (double)a[j][n+1]-(double)a[i][n+1]*a[j][i]/a[i][i];
            a[j][i]= 0;
        }
    }

    fout<<setprecision(out_precision)<<fixed;
    fout<<(double)a[1][n+1]/a[1][1]<<"\n";

    return 0;
}