Pagini recente » Cod sursa (job #764034) | Cod sursa (job #2868789) | Cod sursa (job #331558) | Cod sursa (job #2882012) | Cod sursa (job #801995)
Cod sursa(job #801995)
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
const int N = 260;
const int M = 110000;
const double eps = 0.0001;
int n, m, p, gr[N], a[M], b[M], c[M];
double e[N][N], x[N];
char bu[100];
inline double mabs(double x) {return x > 0 ? x : -x;}
inline bool ver(double x) {
return mabs(x) > eps;
}
void gauss() {
int i = 1, j = 1, k, u, l;
while(i < n && j <= n + 1) {
for(k = i; k<n; ++k)
if(ver(e[k][j]))
break;
if(k != i)
for(u = 1; u<=n + 1; ++u)
swap(e[i][u], e[k][u]);
for(u = j + 1; u<=n + 1; ++u)
e[i][u] /= e[i][j];
e[i][j] = 1;
for(u = i + 1; u<n; ++u) {
for(l = j + 1; l<=n + 1; ++l)
e[u][l] -= e[u][j]*e[i][l];
e[u][j] = 0;
}
++i; ++j;
}
for(i = n - 1; i; --i)
for(j = 1; j<=n + 1; ++j) if(ver(e[i][j])) {
if(j == n + 1) {
cout << "No solution";
return;
}
x[j] = e[i][n + 1];
for(l = j + 1; l<n; ++l)
x[j] -= e[i][l] * x[l];
break;
}
}
int ter() {
int r = 0;
while(bu[p] >= '0' && bu[p] <= '9')
r = r * 10 + bu[p++] - '0';
++p;
return r;
}
int main() {
int i;
freopen("tunel.in", "r", stdin);
freopen("tunel.out", "w", stdout);
cin >> n >> m;
cin.get();
for(i = 1; i<=m; ++i) {
cin.getline(bu, 100); p = 0;
a[i] = ter(); b[i] = ter(); c[i] = ter();
gr[a[i]]++;
gr[b[i]]++;
}
for(i = 1; i<=m; ++i) {
e[a[i]][b[i]] += (double)1/gr[a[i]];
e[b[i]][a[i]] += (double)1/gr[b[i]];
e[a[i]][n + 1] -= (double)c[i]/gr[a[i]];
e[b[i]][n + 1] -= (double)c[i]/gr[b[i]];
}
for(i = 1; i<=n; ++i) {
e[i][i] = -1;
e[i][n] = 0;
}
gauss();
cout << setprecision(4) << fixed << x[1];
return 0;
}