Pagini recente » Cod sursa (job #278896) | Cod sursa (job #1753586) | Cod sursa (job #678298) | Cod sursa (job #522528) | Cod sursa (job #1716293)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int Nmax = 260;
const int Mmax = 100015;
const double epsilon = 10e-8;
int n, m;
int x[Mmax], y[Mmax], cost[Mmax];
int gr[Nmax];
double a[Nmax][Nmax], b[Nmax];
int is0(double a)
{
return (fabs(a) < epsilon);
}
void gauss()
{
int i, j, k;
double d;
for (i = 1; i <= n; ++i)
{
if (is0(a[i][i]))
{
for (j = i; j <= n; ++j)
if (!is0(a[j][i]))
break;
for (k = i; k <= n; ++k)
swap(a[i][k], a[j][k]);
swap(b[i], b[j]);
}
d = a[i][i];
for (j = i; j <= n; ++j)
a[i][j] /= d;
b[i] /= d;
for (j = 1; j <= n; ++j)
if (i != j && !is0(a[j][i]))
{
d = a[j][i];
for (k = i; k <= n; ++k)
a[j][k] -= a[i][k] * d;
b[j] -= b[i] * d;
}
}
}
int main() {
FILE* f = fopen("tunel.in", "r");
FILE* h = fopen("tunel.out", "w");
fscanf(f, "%d %d\n", &n, &m);
for (int i = 1; i <= m; ++i) {
fscanf(f, "%d %d %d\n", &x[i], &y[i], &cost[i]);
++gr[x[i]];
++gr[y[i]];
}
for (int i = 1; i <= n; ++i) {
a[x[i]][x[i]] = -1;
a[y[i]][y[i]] = -1;
}
for (int i = 1; i <= m; ++i) {
b[x[i]] -= (double)cost[i] / gr[x[i]];
a[x[i]][y[i]] += 1.0 / gr[x[i]];
b[y[i]] -= (double)cost[i] / gr[y[i]];
a[y[i]][x[i]] += 1.0/ gr[y[i]];
}
--n;
gauss();
fprintf(h, "%lf\n", b[1]);
return 0;
}