Pagini recente » Cod sursa (job #2831413) | Cod sursa (job #538683) | Cod sursa (job #461359) | Cod sursa (job #3254618) | Cod sursa (job #801658)
Cod sursa(job #801658)
/*
PROB: tunel
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <iomanip>
#define DEBUG
#ifndef DEBUG
#define PRINT(x)
#define D if(0)
#else
#define PRINT(x) \
cout<<#x<<":\t"<<x<<endl
#define D if(1)
#endif
using namespace std;
const char InFile[]="tunel.in";
const char OutFile[]="tunel.out";
const int MaxN=260;
const long double EPS=1e-5;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,M,x,y,c,deg[MaxN];
long double A[MaxN][MaxN],SOL[MaxN];
inline double myabs(const double &x)
{
if(x<0)
{
return -x;
}
return x;
}
inline bool isZero(const double &x)
{
return myabs(x)<EPS;
}
int main()
{
fin>>N>>M;
for(register int i=1;i<=M;++i)
{
fin>>x>>y>>c;
++deg[x];
++deg[y];
++A[x][y];
++A[y][x];
A[x][N+1]-=c;
A[y][N+1]-=c;
}
fin.close();
for(register int i=1;i<=N-1;++i)
{
if(deg[i])
{
for(register int j=1;j<=N+1;++j)
{
A[i][j]/=deg[i];
}
A[i][i]=-1.0;
}
}
for(register int j=1;j<=N+1;++j)
{
A[N][j]=0.0;
}
int i=1,j=1;
while(i<=N && j<=N)
{
int k=i;
for(;k<=N;++k)
{
if(!isZero(A[k][j]))
{
break;
}
}
if(k==N+1)
{
++j;
continue;
}
if(i!=k)
{
for(register int c=1;c<=N+1;++c)
{
swap(A[i][c],A[k][c]);
}
}
for(register int c=j+1;c<=N+1;++c)
{
A[i][c]/=A[i][j];
}
A[i][j]=1.0;
for(register int l=i+1;l<=N;++l)
{
for(register int c=j+1;c<=N+1;++c)
{
A[l][c]-=A[l][j]*A[i][c];
}
A[l][j]=0.0;
}
++i;
++j;
}
for(register int i=N;i>0;--i)
{
for(register int j=1;j<=N;++j)
{
if(!isZero(A[i][j]))
{
SOL[j]=A[i][N+1];
for(register int k=j+1;k<=N;++k)
{
SOL[j]-=SOL[k]*A[i][k];
}
break;
}
}
}
fout<<fixed<<setprecision(5);
fout<<SOL[1];
fout.close();
return 0;
}