Cod sursa(job #2920804)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 25 august 2022 21:38:26
Problema Tunelul groazei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, double> PID;
constexpr int NMAX = 256;
constexpr double eps = 1e-8;

ifstream f ("tunel.in");
ofstream g ("tunel.out");
int N, M;
vector <PID> G[NMAX];

double modul (double x) {
    if (x < 0) x = -x;

    return x;
}

double A[NMAX][NMAX];

void AddEquation (int from, int to, double cost) {
    if (from == N) return;

    A[from][from] ++;
    if (to != N) A[from][to] --;
    A[from][N] += cost;
}

void Read () {
    f >> N >> M;

    for (int i = 1; i <= M; ++ i ) {
        int x, y;
        double C;

        f >> x >> y >> C;

        AddEquation(x, y, C);
        AddEquation(y, x, C);
    }
}

int who1;

void Solve () {
    for (int i = 1; i < N; ++ i ) {
        int j = 0;
        int who = 0;

        for (j = 1; j <= N; ++ j )
            if (modul(A[i][j]) > eps) break;

        if (j == N) {
            cerr << "Wtf ?" << '\n';
            exit(0);
        }

        if (j == N+1) continue;

        who = j;
        if (j == 1) who1 = i;

        for (int j = 1; j < N; ++ j ) {
            if (i != j && modul(A[j][who]) > eps) {
                double factor = A[j][who] / A[i][who];

                for (int k = 1; k <= N; ++ k )
                    A[j][k] -= factor * A[i][k];
            }
        }
    }

    double ans = A[who1][N] / A[who1][1];

    g << setprecision(3) << fixed << ans << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}