Cod sursa(job #310149)

Utilizator istymIstudor Mihai istym Data 1 mai 2009 21:02:23
Problema Tunelul groazei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#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[100010], y[100010];
int cost[100010];

inline double ABS(double a) { return (a > 0) ? (a) : -(a); }

#define DIM 1000000
int poz;
char buf[DIM];




void read()
{
    fread(buf, 1, DIM, stdin);
    cin(n); cin(m);
    for(int i = 1; i <= m; ++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();
	

	int i, j, k;
	for(i = 1; i < n; ++i)
	{
		for(j = 1; 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];
			}
	}
	
    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;
}