Cod sursa(job #2920447)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 24 august 2022 13:23:48
Problema Tunelul groazei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb

#include <bits/stdc++.h>

using namespace std;

const double limit = 1e-8;

int n,m;

double a[265][265];
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[n][i] = 0;
        a[i][n]= 0;
    }
    for(int i=1;i<n;i++)
    {
        poz[i] = 0;
        for(int j=1;j<=n;j++)
        {
            if(abs(a[i][j]) > limit)
            {
                poz[i] = j;
                break;
            }
        }
        for(int l=1;l<n;l++)
        {
            if(i==l)
            {
                continue;
            }
            if(abs(a[l][poz[i]]) < limit)
            {
                continue;
            }
            double fact = 1.0 * a[l][poz[i]] / a[i][poz[i]];
            for(int j=1;j<=n+1;j++)
            {
                a[l][j] -= fact * a[i][j];
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        rez[poz[i]] = 1.0 * a[i][n + 1] / a[i][poz[i]];
    }
}

const int bsize = (1<<16) + 1;
char buffer[bsize];
int p = 0;

void ReadInt(int &nr)
{
    nr = 0;
    while(!isdigit(buffer[p]))
    {
        if(p==bsize-1)
        {
            fread(buffer,1,bsize,stdin);
            p = 0;
        }
        else
        {
            ++p;
        }
    }
    while(isdigit(buffer[p]))
    {
        nr = nr * 10 + buffer[p] - '0';
        if(p==bsize-1)
        {
            fread(buffer,1,bsize,stdin);
            p = 0;
        }
        else
        {
            ++p;
        }
    }
}

int main()
{
    freopen("tunel.in","r",stdin);
    freopen("tunel.out","w",stdout);
    ReadInt(n);
    ReadInt(m);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        ReadInt(x);
        ReadInt(y);
        ReadInt(c);
        Add_edge(x,y,c);
        Add_edge(y,x,c);
    }
    solve_gauss();
    cout<<fixed<<setprecision(6);
    cout<<rez[1]<<'\n';
    return 0;
}