Pagini recente » Cod sursa (job #2431294) | Cod sursa (job #563913) | Cod sursa (job #270802) | Cod sursa (job #2601328) | Cod sursa (job #2595569)
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("tunel.in");
ofstream g("tunel.out");
const int NMAX = 260;
const long double eps = 1e-8;
int N, M;
vector < int > G[NMAX];
int Sum[NMAX];
int Equations, Variables;
long double A[NMAX][NMAX];
long double E[NMAX];
int Chosen[NMAX];
static inline void Add_Edge (int u, int v, int c)
{
G[u].push_back(v);
G[v].push_back(u);
Sum[u] += c;
Sum[v] += c;
return;
}
static inline void Read ()
{
f.tie(nullptr);
f >> N >> M;
while(M--)
{
int u = 0, v = 0, c = 0;
f >> u >> v >> c;
Add_Edge(u, v, c);
}
return;
}
static inline void Load ()
{
E[N] = 0;
Equations = Variables = (N - 1);
for(int i = 1; i < N; ++i)
{
A[i][i] = (int)G[i].size();
for(auto j : G[i])
A[i][j] -= 1;
A[i][N] = Sum[i];
}
return;
}
static inline long double my_abs (long double X)
{
if(X < 0.00000000)
return -X;
return X;
}
static inline void GaussianElimination ()
{
for(int i = 1; i <= Equations; ++i)
{
int pos = 0;
for(int j = 1; j <= Variables + 1 && !pos; ++j)
if(my_abs(A[i][j]) > eps)
pos = j;
if(!pos)
continue;
Chosen[i] = pos;
for(int j = 1; j <= Equations; ++j)
if(i != j && my_abs(A[j][pos]) > eps)
{
long double coef = A[j][pos] / A[i][pos];
for(int k = 1; k <= Variables + 1; ++k)
A[j][k] -= coef * A[i][k];
}
}
return;
}
static inline void Solve ()
{
for(int i = 1; i <= Equations; ++i)
if(Chosen[i])
E[Chosen[i]] = A[i][Variables + 1] / A[i][Chosen[i]];
g << setprecision(6) << fixed << E[1] << '\n';
return;
}
int main()
{
Read();
Load();
GaussianElimination();
Solve();
return 0;
}