Cod sursa(job #1693316)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 22 aprilie 2016 21:01:17
Problema Tunelul groazei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>

using namespace std;

ifstream in("tunel.in");
ofstream out("tunel.out");

const int N = 300;

int n, m;
double gauss[N][N];

void reduce(int x, int y, double c) {
   int i;
   for(i = 0; i <= n; i++) {
      gauss[x][i] -= c * gauss[y][i];
   }
}

void solveGauss() {
   int i, j;
   for(i = 1; i <= n; i++) {
      for(j = 0; j <= n; j++) {
         gauss[i][j] /= gauss[i][i];
      }
      for(j = 1; j <= n; j++) {
         if(j != i) {
            reduce(j, i, gauss[j][i]);
         }
      }
   }
}

void add(int x, int y, int c) {
   gauss[x][y]--;
   gauss[x][x]++;
   gauss[x][0] += c;
}

int main() {
   int i, x, y, c;

   in >> n >> m;

   n--;
   for(i = 1; i <= m; i++) {
      in >> x >> y >> c;
      add(x, y, c);
      add(y, x, c);
   }

   solveGauss();
   out << gauss[1][0] << '\n';

   return 0;
}