Problema 1
Se dau n orase. Se cunoaste distanta dintre oricare doua orase. Un distribuitor de carte cauta sa-si faca un depozit în unul dintre aceste orase. Se cere sa se gaseasca traseul optim de la depozit catre celelalte orase astfel încât distanta totala pe care o va parcurge pentru a distribui în toate celelalte n-1 orase sa fie minima. Sa se precizeze care ar fi orasul în care sa se afle depozitul pentru ca toate celelalte orase sa fie usor accesibile {din acel centru de depozitare sa se poata pleca spre cât mai multe alte orase}.
Rezolvare:
program oras_depozit;
uses crt;
type muchie=record
vf1, vf2, cost:integer;
end;
type vector=array[1..100] of longint;
vector1=array[1..100] of muchie;
matrice=array[1..50,1..50] of longint;
var n, i, j, k, v, cost:integer;
s, t:vector:
x:vector1;
a:matrice;
f:text;
procedure citire;
var i, j, m:integer;
begin
assign (f, ‘depozit.txt’);
reset (f);
readln (f, n); m:=0;
while not eof(f) do
begin
inc(m);
read (f,x[m].vf1);
read (f,x[m].vf2);
read (f,x[m].cost);
end;
for i:=1 to m do
begin
a[x[i].vf1, x[i].vf2:=x[i].cost];
a[x[i].vf2, x[i].vf1:=x[i].cost];
end;
writeln (‘matricea costurilor este:’);
for i:=1 to n do
begin
for j:=1 to n do
write (a[i,j], ‘ ‘);
writeln;
end;
end;
procedure prim;
var i, j, min:integer;
begin
for i:= to n do
s[i]:=v;
s[v]:=0
for i:=1 to n do
t[i]:=0;
cost:=0;
for k:=1 to n-1 do
begin
min:=maxint;
for i:=1 to n do
if (s[i]0) then
if (a[s[i], i]a[i,j]) then
if a [i,j]0 theen
s[i]:=j;
end;
end;
function fii(x:integer):integer;
var k:integer;
begin
k:=0;
for i:=1 to n do
if t[i]=x then
inc(k);
fii:=k;
end;
procedure tata(v:integer);
var i:integer;
begin
for I:=1 to n do
if t[v]=i then
begin
t[i]:=v;
t[v]:=0;
end;
end;
procedure oras;
var max,i,j:integer;
begin
max:=0;
for i:=1 to n do
if fii(i)>max then
max:=fii(i);
writeln(‘orasele optime sunt:’)
for i:=1 to n do
if fii(i)=m