Cod sursa(job #839239)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 21 decembrie 2012 16:07:48
Problema Tunelul groazei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <iomanip>

#define MAX 260
#define EPS 1e-6

using namespace std;

double A[MAX][MAX], X[MAX];
int N, M, a, b, c, grad[MAX];

void solve()
{
    int i = 1, j = 1, k;
    while(i < N && j <= N)
    {
        for(k = i; k <= N; k++) if(A[k][j] > EPS || A[k][j] < -EPS) break;
        if(k == N + 1) {j++; continue;}
        if(i != k) for(int l = 1; l <= N + 1; l++) swap(A[i][l], A[k][l]);
        for(int l = j + 1; l <= N + 1; l++) A[i][l] /= A[i][j];
        A[i][j] = 1;
        for(int u = i + 1; u <= N; u++)
        {
            for(int l = j + 1; l <= N + 1; l++) A[u][l] -= A[u][j] * A[i][l];
            A[u][j] = 0;
        }
        i++; j++;
    }
    for(int i = N; i; i--)
        for(j = 1; j <= N; j++)
            if(A[i][j] > EPS || A[i][j] < -EPS)
            {
                X[j] = A[i][N + 1];
                for(int k = j + 1; k <= N; k++) X[j] -= X[k] * A[i][k];
                break;
            }
}

int main()
{
    ifstream in("tunel.in"); in>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        in>>a>>b>>c;
        grad[a]++; grad[b]++;
        A[a][b]++; A[b][a]++;
        A[a][N + 1] -= c; A[b][N + 1] -= c;
    } in.close();
    for(int i = 1; i < N; i++)
    {
        for(int j = 1; j <= N + 1; j++) A[i][j] /= 1.0 * grad[i];
        A[i][i] = -1;
    }
    for(int i = 1; i <= N + 1; i++) A[N][i] = 0.0;
    solve();
    ofstream out("tunel.out"); out<<fixed<<setprecision(3)<<X[1]; out.close();
    return 0;
}