Cod sursa(job #115779)

Utilizator VmanDuta Vlad Vman Data 16 decembrie 2007 22:37:19
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>

#define Nmax 256
#define Mmax 100001
#define eps 0.000000001

int N,M;
int A[Mmax],B[Mmax],C[Mmax];
double a[Nmax][Nmax];
double b[Nmax],X[Nmax];
int grad[Nmax];

inline double modul(double a) { return a<0?-a:a; }

void citire()
{
 int i;
 freopen("tunel.in","r",stdin);
 scanf("%d %d",&N,&M);
 for (i=1;i<=M;++i)
     {
      scanf("%d %d %d",&A[i],&B[i],&C[i]);
      ++grad[A[i]];
      ++grad[B[i]];
     }
 fclose(stdin);
}

void build()
{
 int i;
 for (i=1;i<=M;++i)
     {
      a[A[i]][B[i]]+=(double)1/grad[A[i]];
      b[A[i]]-=(double)C[i]/grad[A[i]];
      a[B[i]][A[i]]+=(double)1/grad[B[i]];
      b[B[i]]-=(double)C[i]/grad[B[i]];
     }
 for (i=1;i<=N;++i)
     {
      a[i][i]=-1;
      a[i][N]=0;
     }
}

void compute()
{
 int i,j,k;
 double aux,c;
 for (i=1;i<N;++i)
     {
      if (modul(a[i][i])<eps)
      for (j=i+1;j<N;++j)
          if (modul(a[j][i])>eps)
             {
              //schimba liniile intre ele
              for (k=1;k<N;++k)
                {
                 aux=a[i][k];
                 a[i][k]=a[j][k];
                 a[j][k]=aux;
                }
              aux=b[i];
              b[i]=b[j];
              b[j]=b[k];
              break;
             }
      //update
      for (j=i+1;j<N;++j)
          {
           c=(double)a[j][i]/a[i][i];
           for (k=i;k<N;++k)
              {
               a[j][k]=(double)a[j][k]-a[i][k]*c;
              }
           b[j]=(double)b[j]-b[i]*c;
          }
     }
 //calculeaza solutiile
 X[N-1]=(double)b[N-1]/a[N-1][N-1];
 for (i=N-2;i>=1;--i)
     {
      for (j=i+1;j<N;++j)
          b[i]=(double)b[i]-a[i][j]*X[j];
      X[i]=(double)b[i]/a[i][i];
     }
}

int main()
{
 citire();
 build();
 compute();
 freopen("tunel.out","w",stdout);
 printf("%.3lf",X[1]);
 fclose(stdout);
 return 0;
}