Pagini recente » Cod sursa (job #1638795) | Cod sursa (job #2141061) | Cod sursa (job #2050485) | Cod sursa (job #906699) | Cod sursa (job #121622)
Cod sursa(job #121622)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define NMAX 257
#define eps 1e-10
double a[NMAX][NMAX];
int n, m;
double c[NMAX];
short uz[NMAX];
int grad[NMAX];
int x[100100], y[100010];
int cost[100010];
inline double ABS(double a) { return (a > 0) ? (a) : -(a); }
#define DIM 1000000
int poz;
char buf[DIM];
#define cin(x) \
{ \
x = 0; \
while(buf[poz] > '9' || buf[poz] < '0') \
if(++poz == DIM) \
poz = 0, fread(buf, 1, DIM, stdin); \
while(buf[poz] >= '0' && buf[poz] <= '9') \
{ \
x = x*10 + (buf[poz]-'0'); \
if(++poz == DIM) poz = 0, fread(buf, 1, DIM, stdin); \
} \
}
void read()
{
fread(buf, 1, DIM, stdin);
//scanf("%d %d", &n, &m);
cin(n); cin(m);
for(int i = 1; i <= m; ++i)
{
//scanf("%d %d %lf", &x[i], &y[i], &cost[i]);
cin(x[i]); cin(y[i]); cin(cost[i]);
++grad[x[i]], ++grad[y[i]];
}
for(int i = 1; i <= m; ++i)
{
a[x[i]][y[i]] += (double)1/grad[x[i]];
c[x[i]] -= (double)cost[i]/grad[x[i]];
a[y[i]][x[i]] += (double)1/grad[y[i]];
c[y[i]] -= (double)cost[i]/grad[y[i]];
}
for(int i = 1; i <= n; ++i)
a[i][i] = -1, a[i][n] = 0;
}
void print()
{
printf("%d\n", n);
int i, j;
for(i = 1; i <= n; ++i, printf("\n"))
{
for(j = 1; j <= n; ++j)
printf("%lf ", a[i][j]);
printf("%lf ", c[i]);
}
}
int main()
{
freopen("tunel.in", "r", stdin);
freopen("tunel.out", "w", stdout);
read();
//print();
// return 0;
int i, j, k;
for(i = 1; i < n; ++i)
{
for(j = i; j < n; ++j)
if(ABS(a[j][i]) > eps)
break;
double aux;
if(i != j)
for(k = 1; k < n; ++k)
{
aux = a[i][k];
a[i][k] = a[j][k];
a[j][k] = aux;
}
aux = c[i];
c[i] = c[j];
c[j] = aux;
for(j = 1; j < n; ++j)
if(j != i)
{
if(ABS(a[j][i]) < eps) continue;
double f = (double)a[i][i]/a[j][i];
for(k = 1; k < n; ++k)
a[j][k] = a[j][k]*f - a[i][k];
c[j] = c[j]*f - c[i];
}
}
//print();
//printf("%.3lf\n", s);
if(a[1][1] > eps)
printf("%.3lf\n", (double)c[1]/a[1][1]);
else if(a[1][1] < eps && c[1] < eps)
printf("%.3lf\n", (double)c[1]/a[1][1]);
else
printf("%.3lf\n", (double)(-c[1])/(-a[1][1]));
return 0;
}