Cod sursa(job #1716293)

Utilizator usermeBogdan Cretu userme Data 12 iunie 2016 13:48:37
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int Nmax = 260;
const int Mmax = 100015;

const double epsilon = 10e-8;

int n, m;
int x[Mmax], y[Mmax], cost[Mmax];
int gr[Nmax];
double a[Nmax][Nmax], b[Nmax];

int is0(double a)
{
    return (fabs(a) < epsilon);
}

void gauss()
{
    int i, j, k;
    double d;

    for (i = 1; i <= n; ++i)
    {
        if (is0(a[i][i]))
        {
            for (j = i; j <= n; ++j)
                if (!is0(a[j][i]))
                    break;

            for (k = i; k <= n; ++k)
                swap(a[i][k], a[j][k]);
            swap(b[i], b[j]);
        }

        d = a[i][i];

        for (j = i; j <= n; ++j)
            a[i][j] /= d;
        b[i] /= d;

        for (j = 1; j <= n; ++j)
            if (i != j && !is0(a[j][i]))
            {
                d = a[j][i];
                for (k = i; k <= n; ++k)
                    a[j][k] -= a[i][k] * d;
                b[j] -= b[i] * d;
            }
    }
}

int main() {
    FILE* f = fopen("tunel.in", "r");
    FILE* h = fopen("tunel.out", "w");
    fscanf(f, "%d %d\n", &n, &m);
    for (int i = 1; i <= m; ++i) {
        fscanf(f, "%d %d %d\n", &x[i], &y[i], &cost[i]);
        ++gr[x[i]];
        ++gr[y[i]];
    }
    for (int i = 1; i <= n; ++i) {
        a[x[i]][x[i]] = -1;
        a[y[i]][y[i]] = -1;
    }
    for (int i = 1; i <= m; ++i) {
        b[x[i]] -= (double)cost[i] / gr[x[i]];
        a[x[i]][y[i]] += 1.0 / gr[x[i]];
        b[y[i]] -= (double)cost[i] / gr[y[i]];
        a[y[i]][x[i]] += 1.0/ gr[y[i]];
    }
    --n;
    gauss();
    fprintf(h, "%lf\n", b[1]);
    return 0;
}