Pagini recente » Cod sursa (job #908249) | Cod sursa (job #18968) | Cod sursa (job #450185) | Cod sursa (job #78488) | Cod sursa (job #1830489)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 260;
int n, m, x, y, t, edge[Nmax][Nmax], i, j, k, nr, sum, p;
double a[Nmax][Nmax], coef;
bool nenul(double x)
{
return max(x, -x) > 0.0000001;
}
int main()
{
freopen("tunel.in", "r", stdin);
freopen("tunel.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
edge[i][j] = -1;
for(i=1; i<=m; ++i)
{
scanf("%d%d%d", &x, &y, &t);
edge[x][y] = edge[y][x] = t;
}
for(i=1; i<n; ++i)
{
nr = sum = 0;
for(j=1; j<=n; ++j)
if(edge[i][j]!=-1)
{
++nr;
sum += edge[i][j];
}
a[i][i] = nr*1.0;
for(j=1; j<n; ++j)
if(edge[i][j]!=-1)
a[i][j] = -1.0;
a[i][n] = sum*1.0;
}
for(i=1; i<n; ++i)
{
for(p=1; p<n; ++p)
if(nenul(a[i][p])) break;
for(j=1; j<n; ++j)
if(i!=j && nenul(a[j][p]))
{
coef = a[j][p] / a[i][p];
for(k=1; k<=n; ++k)
a[j][k] -= coef * a[i][k];
}
}
for(i=1; i<=n; ++i)
if(nenul(a[i][1]))
printf("%.3lf\n", a[i][n] / a[i][1]);
return 0;
}