Cod sursa(job #1829059)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 14 decembrie 2016 11:51:31
Problema Tunelul groazei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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-5

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 = 1; i <= n; i ++ )
        eq[i].resize( 1 + MAX_N + 1 );

    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 ++ ) {
        for ( j : g[i] ) {
            eq[i][j] += 1;
            eq[i][i] -= 1;
        }

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

    for ( i = 1, j = 1; j <= n; j ++ ) {
        k = i;
        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 )
                    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;
//    }

    fout << eq[1][n + 1] / -eq[1][1];

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

    return 0;
}