Pagini recente » Cod sursa (job #1635629) | Cod sursa (job #1643774) | Cod sursa (job #1421752) | Cod sursa (job #2696032) | Cod sursa (job #2920804)
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, double> PID;
constexpr int NMAX = 256;
constexpr double eps = 1e-8;
ifstream f ("tunel.in");
ofstream g ("tunel.out");
int N, M;
vector <PID> G[NMAX];
double modul (double x) {
if (x < 0) x = -x;
return x;
}
double A[NMAX][NMAX];
void AddEquation (int from, int to, double cost) {
if (from == N) return;
A[from][from] ++;
if (to != N) A[from][to] --;
A[from][N] += cost;
}
void Read () {
f >> N >> M;
for (int i = 1; i <= M; ++ i ) {
int x, y;
double C;
f >> x >> y >> C;
AddEquation(x, y, C);
AddEquation(y, x, C);
}
}
int who1;
void Solve () {
for (int i = 1; i < N; ++ i ) {
int j = 0;
int who = 0;
for (j = 1; j <= N; ++ j )
if (modul(A[i][j]) > eps) break;
if (j == N) {
cerr << "Wtf ?" << '\n';
exit(0);
}
if (j == N+1) continue;
who = j;
if (j == 1) who1 = i;
for (int j = 1; j < N; ++ j ) {
if (i != j && modul(A[j][who]) > eps) {
double factor = A[j][who] / A[i][who];
for (int k = 1; k <= N; ++ k )
A[j][k] -= factor * A[i][k];
}
}
}
double ans = A[who1][N] / A[who1][1];
g << setprecision(3) << fixed << ans << '\n';
}
int main () {
Read();
Solve();
return 0;
}