Pagini recente » Cod sursa (job #2096584) | Cod sursa (job #1754485) | Borderou de evaluare (job #2051260) | Cod sursa (job #1401461) | Cod sursa (job #1829059)
# 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;
}