Cod sursa(job #2919682)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 18 august 2022 18:04:58
Problema Tunelul groazei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("tunel.in");
ofstream g("tunel.out");

const long double limit = 1e-9;

int n,m;

long double a[265][265];
long double rez[265];

int poz[265];

void Add_edge(int x, int y, int c)
{
    ++a[y][y];
    --a[y][x];
    a[y][n+1] += c;
}

void solve_gauss()
{
    for(int i=1;i<=n+1;i++)
    {
        a[1][i] = 0;
        a[i][1] = 0;
    }
    for(int i=2;i<=n;i++)
    {
        poz[i] = 0;
        for(int j=2;j<=n;j++)
        {
            if(abs(a[i][j]) > limit)
            {
                poz[i] = j;
                break;
            }
        }
        for(int l=2;l<=n;l++)
        {
            if(i==l)
            {
                continue;
            }
            if(abs(a[l][poz[i]]) < limit)
            {
                continue;
            }
            long double fact = 1.0 * a[l][poz[i]] / a[i][poz[i]];
            for(int j=2;j<=n+1;j++)
            {
                a[l][j] -= fact * a[i][j];
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        rez[poz[i]] = 1.0 * a[i][n + 1] / a[i][poz[i]];
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        Add_edge(x,y,c);
        Add_edge(y,x,c);
    }
    solve_gauss();
    g<<fixed<<setprecision(3);
    g<<rez[n]<<'\n';
    return 0;
}