Pagini recente » Cod sursa (job #187082) | Cod sursa (job #2145835) | Cod sursa (job #801944) | Cod sursa (job #249973) | Cod sursa (job #793941)
Cod sursa(job #793941)
#include <fstream>
#include <iomanip>
using namespace std;
const int Nmax = 265;
double EPS=0.0000001;
int N,M;
double A[Nmax][Nmax];
double X[Nmax];
int Grad[Nmax];
ifstream F("tunel.in");
ofstream G("tunel.out");
int main()
{
F>>N>>M;
for (int i=1,x,y,c;i<=M;++i)
{
F>>x>>y>>c;
++Grad[x], ++Grad[y];
++A[x][y], ++A[y][x];
A[x][N+1] -= c, A[y][N+1] -= c;
}
for (int i=1;i<=N;++i)
{
for(int j=1;j<=N+1;++j)
A[i][j]/=(double)Grad[i];
A[i][i]=-1.0;
}
for(int i=1;i<=N+1;++i)
A[N][i]=0.0;
for (int i=1,j=1,k;i<=N && j<=N;++i,++j)
{
for ( k=i;k<=N;++k )
if ( A[k][j]<-EPS || A[k][j]>EPS )
break;
if ( k==N+1 )
{
--i;
continue;
}
if ( i != k )
for (int l=1;l<=N+1;++l)
swap(A[i][l],A[k][l]);
for (int l=j+1;l<=N+1;++l)
A[i][l] /= A[i][j];
A[i][j]=1.0;
for(int u=i+1;u<=N;++u)
{
for(int l=j+1;l<=N+1;++l)
A[u][l]-=A[u][j]*A[i][l];
A[u][j] = 0.0;
}
}
for (int i=N-1;i;--i)
{
bool Ok=0;
for (int j=1;j<=N+1 && !Ok;++j)
if ( A[i][j]>EPS || A[i][j]<-EPS )
{
Ok=1, X[j]=A[i][N+1];
for (int k=j+1;k<=N;k++)
X[j]-=X[k]*A[i][k];
}
}
G<<fixed<<setprecision(8)<<X[1]<<'\n';
F.close();
G.close();
return 0;
}