Cod sursa(job #331250)

Utilizator razvan2006razvan brezulianu razvan2006 Data 13 iulie 2009 12:59:19
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>  
#include <cmath>  
#include <algorithm>  
  
using namespace std;  
  
#define Nmax 256  
#define Mmax 100015  
  
const double eps = 10e-8;  
  
int n, m;  
int x[Mmax], y[Mmax], cost[Mmax];  
int gr[Nmax];  
double a[Nmax][Nmax], b[Nmax];  
  
void citire()  
{  
    int i;  
  
    scanf("%d %d\n", &n, &m);  
    for (i = 1; i <= m; ++i)  
    {  
        scanf("%d %d %d\n", &x[i], &y[i], &cost[i]);  
        ++gr[x[i]], ++gr[y[i]];  
    }  
}  
  
int is0(double a)  
{  
    return (fabs(a) < eps);  
}  
  
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;  
            }  
    }  
}  
  
void solve()  
{  
    int i;  
  
    for (i = 1; i <= n; ++i)  
    {  
        a[x[i]][x[i]] = -1;  
        a[y[i]][y[i]] = -1;  
    }  
  
    for (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();  
  
    printf("%lf\n", b[1]);  
}  
  
int main()  
{  
    freopen("tunel.in", "r", stdin);  
    freopen("tunel.out", "w", stdout);  
  
    citire();  
    solve();  
  
    return 0;  
}