Cod sursa(job #1830489)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 16 decembrie 2016 19:45:54
Problema Tunelul groazei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 260;

int n, m, x, y, t, edge[Nmax][Nmax], i, j, k, nr, sum, p;
double a[Nmax][Nmax], coef;

bool nenul(double x)
{
    return max(x, -x) > 0.0000001;
}

int main()
{
    freopen("tunel.in", "r", stdin);
    freopen("tunel.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            edge[i][j] = -1;

    for(i=1; i<=m; ++i)
    {
        scanf("%d%d%d", &x, &y, &t);
        edge[x][y] = edge[y][x] = t;
    }

    for(i=1; i<n; ++i)
    {
        nr = sum = 0;

        for(j=1; j<=n; ++j)
            if(edge[i][j]!=-1)
            {
                ++nr;
                sum += edge[i][j];
            }

        a[i][i] = nr*1.0;

        for(j=1; j<n; ++j)
            if(edge[i][j]!=-1)
                a[i][j] = -1.0;

        a[i][n] = sum*1.0;
    }

    for(i=1; i<n; ++i)
    {
        for(p=1; p<n; ++p)
            if(nenul(a[i][p])) break;

        for(j=1; j<n; ++j)
        if(i!=j && nenul(a[j][p]))
        {
            coef = a[j][p] / a[i][p];
            for(k=1; k<=n; ++k)
                a[j][k] -= coef * a[i][k];
        }
    }

    for(i=1; i<=n; ++i)
        if(nenul(a[i][1]))
            printf("%.3lf\n", a[i][n] / a[i][1]);

    return 0;
}