Cod sursa(job #2918782)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 12 august 2022 22:49:52
Problema Tunelul groazei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("tunel.in");
ofstream fout("tunel.out");

const int NMAX=260;

const double eps=1e-6;

double mat[NMAX][NMAX],sol[NMAX];

int n,m,i,j,k;

void citire()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int u,v,c;
        fin>>u>>v>>c;
        mat[u][n+1]+=c;mat[v][n+1]+=c;
        mat[u][v]--;mat[v][u]--;
        mat[u][u]++;mat[v][v]++;
    }
    for(i=1;i<=n+1;i++)
        mat[n][i]=0;
}

void myswap(double &a, double &b)
{
    double c=a;
    a=b;
    b=c;
}

void swaplines(int l1, int l2)
{
    for(int i=1;i<=n+1;i++)
        myswap(mat[l1][i],mat[l2][i]);
}

void gauss()
{
    i=1;j=1;
    while(i<=n&&j<=n)
    {
        for(k=i;k<=n;k++)
            if(mat[k][j]<-eps||mat[k][j]>eps)
                break;
        if(k==n+1){j++;continue;}
        if(k!=i)swaplines(i,k);
        for(k=n+1;k>=j;k--)
            mat[i][k]/=mat[i][j];
        for(k=i+1;k<=n;k++)
            for(int l=n+1;l>=j;l--)
                mat[k][l]-=mat[k][j]*mat[i][l];
        i++;j++;
    }
    for(i=n-1;i>=1;i--)
        for(j=1;j<=n+1;j++)
            if(mat[i][j]<-eps||mat[i][j]>eps)
            {
                if(j==n+1)
                {
                    fout<<"Imposibil\n";
                    exit(0);
                }
                sol[j]=mat[i][n+1];
                for(k=j+1;k<=n;k++)
                    sol[j]-=sol[k]*mat[i][k];
                break;
            }
}

signed main()
{
    citire();
    gauss();
    fout<<fixed<<setprecision(3)<<sol[1]<<'\n';
    return 0;
}