Cod sursa(job #132661)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 6 februarie 2008 12:42:33
Problema Tunelul groazei Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.79 kb
const e=0.00000001;
var fi,fo:text;
    coef:array[1..260,1..260]of extended;
    v1,v2,c:array[1..100010]of longint;
    muchii:array[1..260]of longint;
    B:array[1..260]of extended;
    n,m,i,j,k:longint;
    factor:real;
procedure swap(var a,b:extended);
var aux:extended;
begin
  aux:=a;
  a:=b;
  b:=aux;
end;
function verif(poz:longint):boolean;
var k:longint;
begin
  verif:=true;
  for k:=poz to n-1 do
    if abs(coef[k,poz])>e then
      begin
        verif:=false;
        exit;
      end;
end;
procedure gauss;
begin
  for i:=1 to n-1 do
    begin
      if (abs(coef[i,i])<e)and(not verif(i)) then
        begin
          for k:=i to n-1 do
            swap(coef[i,k],coef[j,k]);
          swap(B[i],B[j]);
        end;
      factor:=coef[i,i];
      for k:=i to n-1 do
        coef[i,k]:=coef[i,k]/factor;
      B[i]:=B[i]/factor;
      for k:=1 to n-1 do
        if (k<>i)and(abs(coef[k,i])>0) then
          begin
            factor:=coef[k,i];
            for j:=i to n-1 do
              coef[k,j]:=coef[k,j]-coef[i,j]*factor;
            B[k]:=B[k]-B[i]*factor;
          end;
     end;
end;
procedure construct;
begin
  read(fi,n,m);
  for i:=1 to m do
    begin
      read(fi,v1[i],v2[i],c[i]);
      muchii[v1[i]]:=muchii[v1[i]]+1;
      muchii[v2[i]]:=muchii[v2[i]]+1;
    end;
  for i:=1 to m do
    begin
      coef[v1[i],v2[i]]:=coef[v1[i],v2[i]]+1/muchii[v1[i]];
      B[v1[i]]:=B[v1[i]]-c[i]/muchii[v1[i]];
      coef[v2[i],v1[i]]:=coef[v2[i],v1[i]]+1/muchii[v2[i]];
      B[v2[i]]:=B[v2[i]]-c[i]/muchii[v2[i]];
    end;
  for i:=1 to n do
    coef[i,i]:=-1;
end;
begin
  assign(fi,'tunel.in'); reset(fi);
  assign(fo,'tunel.out'); rewrite(fo);
  construct;
  gauss;
  writeln(fo,B[1]:0:5);
  close(fi);
  close(fo);
end.