Cod sursa(job #2595569)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 7 aprilie 2020 21:54:21
Problema Tunelul groazei Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#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;
}