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ă).