Pagina principala | Inscriere | Autentificare | Probleme | Runde | Clasament | Anunturi | Echipa | Regulament | Exit


Vizualizare solutie pentru problema: tramvai

Titlul problemei tramvai
Grupa Grupa B
Problema numarul 1
Runda numarul 5
Solutie oficiala {$D+,E+,I+,L+,N-,O-,P-,Q-,R+,T-,V+,X+,Y+}
{$M 65384,0,655360}
const fi='tramvai.in';fo='tramvai.out';
type muchie=record i,j:byte; cost:integer end;
var f:text;
a:array[1..100,1..100]of boolean;
m:array[1..5000]of muchie;
comp:array[1..100]of byte;
n,s,ntot:word; tot:longint;
procedure citeste;
var i,j,k,c1,c2:integer;
begin
assign(f,fi);reset(f);
readln(f,n,s);
for k:=1 to s do
with m[k] do begin
readln(f,i,j,c1,c2);
a[i,j]:=true;a[j,i]:=true;
cost:=c1-c2
end;
close(f);
for i:=1 to n do
for j:=i+1 to n do
if not a[i,j] then begin
inc(s);m[s].cost:=0;
m[s].i:=i;m[s].j:=j;
end;
end;
procedure rezolva;
var i,j,k,l:word;
c1,c2:integer;
aux:muchie;
begin
for i:=1 to s-1 do
for j:=i+1 to s do
if m[i].cost>m[j].cost then begin
aux:=m[i];m[i]:=m[j];m[j]:=aux
end;
fillchar(a,sizeof(a),false);
for i:=1 to n do comp[i]:=i;
for i:=1 to s do
if comp[m[i].i]<>comp[m[i].j] then begin
a[m[i].i,m[i].j]:=true;
a[m[i].j,m[i].i]:=true;
inc(ntot);if ntot=n-1 then break;
k:=comp[m[i].i];
l:=comp[m[i].j];
for j:=1 to n do
if comp[j]=k then comp[j]:=l
end;
if ntot assign(f,fo);
rewrite(f);
writeln(f,'NU')
end
else begin
for k:=1 to s do
if m[k].cost<0 then begin
a[m[k].i,m[k].j]:=true;
a[m[k].j,m[k].i]:=true
end;
assign(f,fi); reset(f);
readln(f,n,s);
for k:=1 to s do begin
readln(f,i,j,c1,c2);
if a[i,j] then inc(tot,c1) else inc(tot,c2);
end;
close(f);
assign(f,fo);rewrite(f);
writeln(f,tot);
{for i:=1 to n-1 do
for j:=i+1 to n do
if a[i,j] then writeln(f,i,' ',j);
}
end;
close(f)
end;
begin
citeste;
rezolva;
end.
Explicatii despre modul de punctare S-au acordat 5 puncte pentru fiecare test, cu exceptia testului 9, punctat cu 10 puncte.

Download arhiva teste de intrare  

Click aici pentru a va intoarce

© 2002 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com