|
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 |