Cod sursa(job #1829064)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 14 decembrie 2016 12:03:04
Problema Tunelul groazei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
# include <iostream>
# include <fstream>
# include <valarray>
# include <vector>

using namespace std;

# define MAX_N 255

valarray<double> eq[1 + MAX_N];
vector<int> g[1 + MAX_N];
int s[1 + MAX_N];

# define EPS 1e-7

inline bool null( double x )
{
    return abs( x ) <= EPS;
}

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

    int n, m, i, j, k, a, b, c;

    fin >> n >> m;

    for ( i = 0; i < m; i ++ ) {
        fin >> a >> b >> c;

        g[a].push_back( b );
        g[b].push_back( a );

        s[a] += c;
        s[b] += c;
    }

    for ( i = 1; i < n; i ++ ) {
        eq[i].resize( 1 + MAX_N + 1 );

        for ( int j : g[i] ) {
            eq[i][j] += 1;
            eq[i][i] -= 1;
        }

        eq[i][n + 1] = s[i];
    }

    eq[n].resize( 1 + MAX_N + 1 );
    eq[n][n] = -1;

    for ( i = 1, j = 1; j <= n; j ++ ) {

        k = 1;
        while ( k <= n && null( eq[k][j] ) )
            k ++;

        if ( k <= n ) {
            if ( k != i )
                swap( eq[i], eq[k] );

            for ( k = 1; k <= n; k ++ )
                if ( k != i && !null( eq[k][j] ) )
                    eq[k] -= eq[i] * ( eq[k][j] / eq[i][j] );

            i ++;
        }
    }

//    for ( i = 1; i <= n; i ++ ) {
//        for ( j = 1; j <= n + 1; j ++ )
//            cout << eq[i][j] << ' ';
//
//        cout << endl;
//    }

    i = 1;
    while ( null( eq[i][1] ) )
        i ++;
    fout << eq[i][n + 1] / -eq[i][1];

    fin.close();
    fout.close();

    return 0;
}