Cod sursa(job #253349)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 18:15:07
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
 #include <stdio.h>  
 #include <algorithm>  
   
 using namespace std;  
   
 #define nm 256  
   
 int n, m, a, b, c, i;  
 double C[nm][nm];  
 double g[nm];  
 double sol;  
   
   
 void read()  
   
 {  
     scanf("%d %d ", &n, &m);  
     for (i=1; i<=m; ++i)  
     {  
         scanf("%d %d %d ", &a, &b, &c);  

         ++ g[a];  
         ++ g[b];  
         -- C[a][b];  
         -- C[b][a];  
         C[a][n+1] += c;  
         C[b][n+1] += c;  
     }  
 }  
   
   
 void gauss()  
   
 {  
     int i, j, k;  
   
     for (i=1; i<n; ++i)  
     {  
         for (j=i; C[i][j] == 0; ++j);  
         if (j != i)  
         {  
             for (k=1; k<=n+1; ++k)  
                 swap(C[i][k], C[j][k]);  
         }  
         for (j=1; j<=n; ++j)  
         {  
             if (j != i)  
             {  
                 double ratio = C[j][i] / C[i][i];  
                   
                 for (k=1; k<=n+1; ++k)  
                 {  
                     C[j][k] -= (C[i][k] * ratio);  
                 }  
             }  
         }  
     }  
 }  
   
   
 void solve()  
   
 {  
     for (i=1; i<=n; ++i)  
     {  
         C[i][i] = g[i];  
     }  
     gauss();  
     sol = C[1][n+1] / C[1][1];  
 
 }  
   
   
 void write()  
   
 {  
     printf("%lf\n", sol);  
 }  
   
   
 int main()  
   
 {  
     freopen("tunel.in", "r", stdin);  
     freopen("tunel.out","w",stdout);  
   
     read();  
     solve();  
     write();  
   
     return 0;  
}