Pagini recente » Cod sursa (job #131389) | Cod sursa (job #2072786) | Cod sursa (job #1047852) | Cod sursa (job #1780396) | Cod sursa (job #839239)
Cod sursa(job #839239)
#include <fstream>
#include <iomanip>
#define MAX 260
#define EPS 1e-6
using namespace std;
double A[MAX][MAX], X[MAX];
int N, M, a, b, c, grad[MAX];
void solve()
{
int i = 1, j = 1, k;
while(i < N && j <= N)
{
for(k = i; k <= N; k++) if(A[k][j] > EPS || A[k][j] < -EPS) break;
if(k == N + 1) {j++; 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;
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;
}
i++; j++;
}
for(int i = N; i; i--)
for(j = 1; j <= N; j++)
if(A[i][j] > EPS || A[i][j] < -EPS)
{
X[j] = A[i][N + 1];
for(int k = j + 1; k <= N; k++) X[j] -= X[k] * A[i][k];
break;
}
}
int main()
{
ifstream in("tunel.in"); in>>N>>M;
for(int i = 1; i <= M; i++)
{
in>>a>>b>>c;
grad[a]++; grad[b]++;
A[a][b]++; A[b][a]++;
A[a][N + 1] -= c; A[b][N + 1] -= c;
} in.close();
for(int i = 1; i < N; i++)
{
for(int j = 1; j <= N + 1; j++) A[i][j] /= 1.0 * grad[i];
A[i][i] = -1;
}
for(int i = 1; i <= N + 1; i++) A[N][i] = 0.0;
solve();
ofstream out("tunel.out"); out<<fixed<<setprecision(3)<<X[1]; out.close();
return 0;
}