Pagini recente » Cod sursa (job #3209099) | Cod sursa (job #10686) | Cod sursa (job #38950) | Cod sursa (job #2126098) | Cod sursa (job #130888)
Cod sursa(job #130888)
#include <cstdio>
#include <cmath>
#include <cstring>
#define FIN "tunel.in"
#define FOUT "tunel.out"
#define MAX_N 260
#define MAX_M 10005
const double eps = 0.00000001;
int N, M, i;
int a[MAX_M];
int b[MAX_M];
int c[MAX_M];
int v[MAX_N];
double A[MAX_N][MAX_N];
double B[MAX_N];
void solve()
{
int i, j, k;
double d;
for (i = 1; i <= N; ++i)
{
A[a[i]][a[i]] = A[b[i]][b[i]] = -1;
}
for (i = 1; i <= M; ++i)
{
B[a[i]] = double(B[a[i]] - (double)c[i] / v[a[i]]);
B[b[i]] = double(B[b[i]] - (double)c[i] / v[b[i]]);
A[a[i]][b[i]] = double(A[a[i]][b[i]] + 1.0 / v[a[i]]);
A[b[i]][a[i]] = double(A[b[i]][a[i]] + 1.0/ v[b[i]]);
}
N = N - 1;
for (i = 1; i <= N; ++i)
{
if (fabs(A[i][i]) < eps)
{
for (k = i; k <= N; ++k) if (!(fabs(A[k][i]) < eps)) break;
for (k = i; k <= N; ++k)
{
double ax = A[i][k];
A[i][k] = A[j][k];
A[j][k] = ax;
}
double ax = B[i];
B[i] = B[j];
B[j] = ax;
}
d = A[i][i];
for (j = i; j <= N; ++j) A[i][j] = double (A[i][j]/d);
B[i] = double (B[i]/d);
for (j = 1; j <= N; ++j)
if (i != j && !(fabs(A[j][i]) < 0))
{
d = A[j][i];
for (k = i; k <= N; ++k) A[j][k] = double (A[j][k] - A[i][k] * d);
B[j] = double(B[j] - B[i] * d);
}
}
printf("%lf\n", (double)B[1]);
}
int main()
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d %d", &N, &M);
for (i = 1; i <= M; ++i)
{
scanf("%d %d %d", a + i, b + i, c + i);
v[a[i]]++;
v[b[i]]++;
}
solve();
return 0;
}