Cod sursa(job #130887)

Utilizator floringh06Florin Ghesu floringh06 Data 2 februarie 2008 14:10:04
Problema Tunelul groazei Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>  
#include <cmath>  
#include <cstring>  
  
#define FIN "tunel.in"
#define FOUT "tunel.out"  
#define MAX_N 260  
#define MAX_M 10005  
#define eps 0.00000001  
  
int N, M, i;  
int a[MAX_M];
int b[MAX_M];
int c[MAX_M];  
int v[MAX_N];  

double A[MAX_N][MAX_N];
double B[MAX_N];  
    
    void solve()  
    {  
         int i, j, k;  
         double d;
  
         for (i = 1; i <= N; ++i)  
         {  
             A[a[i]][a[i]] = A[b[i]][b[i]] = -1;  
         }  
  
         for (i = 1; i <= M; ++i)  
         {  
                B[a[i]] = double(B[a[i]] - (double)c[i] / v[a[i]]);  
                B[b[i]] = double(B[b[i]] - (double)c[i] / v[b[i]]);  
                
                A[a[i]][b[i]] = double(A[a[i]][b[i]] + 1.0 / v[a[i]]);  
                A[b[i]][a[i]] = double(A[b[i]][a[i]] + 1.0/ v[b[i]]);  
         }  
         N = N - 1;  
  
         for (i = 1; i <= N; ++i)  
         {  
             if (fabs(A[i][i]) < eps)  
             {  
                 for (k = i; k <= N; ++k) if (!(fabs(A[k][i]) < eps)) break;  
                 for (k = i; k <= N; ++k)  
                 {
                     double ax = A[i][k];
                     A[i][k] = A[j][k];  
                     A[j][k] = ax;
                 }
                 double ax = B[i];
                 B[i] = B[j];  
                 B[j] = B[i];
             }  
  
             d = A[i][i];  
  
             for (j = i; j <= N; ++j)  A[i][j] = double (A[i][j]/d);  
             B[i] = double (B[i]/d);  
  
             for (j = 1; j <= N; ++j)  
                 if (i != j && !(fabs(A[j][i]) < 0))  
                 {  
                    d = A[j][i];  
                    for (k = i; k <= N; ++k) A[j][k] = double (A[j][k] - A[i][k] * d);  
                    B[j] = double(B[j] - B[i] * d);  
                 }  
         }  
         printf("%lf\n", (double)B[1]);  
    }  
  
    int main()  
    {  
        freopen(FIN, "r", stdin);  
        freopen(FOUT, "w", stdout);  
  
        scanf("%d %d", &N, &M);  
        for (i = 1; i <= M; ++i)  
        {  
            scanf("%d %d %d", a + i, b + i, c + i);  
            v[a[i]]++; 
            v[b[i]]++;  
        }  

        solve();  
  
        return 0;  
    }