Probleme propuse

 

1. Se dă un graf neorientat care are pe fiecare muchie un cost. Să se determine arborele parţial de cost minim al grafului respectiv.

 

2. Într-un oraş există mai multe şcoli. Între aceste şcoli există drumuri, pe fiecare drum fiind nevoie de plata unei taxe pentru a putea merge pe acel drum. Primarul oraşului doreşte însă ca suma tuturor taxelor care trebuie plătite să fie minimă. Pentru acest lucru el are nevoie de un elev isteţ care să îi spună care străzi să le închidă, astfel încât să existe drum între oricare două şcoli, pentru ca suma taxelor de pe străzile rămase să fie minimă. Datele se citesc dintr-un fişier de intrare astfel: pe prima linie se află numărul de şcoli din oraşul respectiv, n; până la sfârşitul fişierului se află, câte una pe linie, perechi de forma (i,j,c) cu semnificaţia: „există legătură între şcoala i şi şcoala j, iar taxa pentru parcurgerea acestei legături este c”. Datele se ieşire se vor scrie într-un fişier astfel: pe fiecare linie a fişierului se vor afla două numere (i,j) cu semnificaţia „legatura dintre şcoala i şi şcoala j trebuie păstrată”. Se garantează că iniţial există drum de la oricare şcoală la oricare şcoală (nu neaparat legătură directă).