Pagini recente » Cod sursa (job #2539905) | Cod sursa (job #792748) | Cod sursa (job #871716) | Cod sursa (job #1937230) | Cod sursa (job #115779)
Cod sursa(job #115779)
#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;
}