Page 120 - MATINF Nr. 11-12

˘
120 PROBLEME DE INFORMATICA PENTRU CONCURSURI

Exemplu

grhamilton.in grhamilton.out Explicat , ie
4 6 DA Ciclul hamiltonian 1 2 4 3
1 2 10 1 2 4 3 1 1 are costul cel mai mic:
1 4 100 10+10+20+15 = 55.
1 3 15
2 4 10
2 3 100
4 3 20

Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘ disponibil˘ 2 MB.
a
a
Maria Crina Diaconu, Pites , ti

a
I 148 (tareconex). Se d˘ un graf orientat cu n noduri s , i m arce. Pentru acest graf se dores , te
a
determinarea num˘arului minim de arce, notat cu NrMin, care dac˘ se adaug˘ se obt , ine un graf
a
tare conex.
a
Cerint , ˘
Cunoscˆand n, m s , i cele m arce se cere s˘ se determine num˘arul NrMin definit ˆın enunt , .
a
Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 100.

Date de intrare

Fis , ierul tareconex.in cont , ine pe prima linie n s , i m separate printr-un spat , iu, apoi pe
urm˘atoarele m linii nodurile arcelor separate prin cˆate un spat , iu.

Date de ie¸sire

Fis , ierul de ies , ire tareconex.out va cont , ine pe prima linie NrMax.

Exemplu

tareconex.in tareconex.out Explicat , ie
6 7 2 Ca s˘a obt , inem graf tare
1 4 conex, spre exemplu putem
4 6 ad˘auga arcele (2,6) s , i (5,3).
6 1
2 5
3 5
5 2
6 2

Timp maxim de execut , ie: 1 secund˘a/test.
Memorie total˘ disponibil˘ 2 MB.
a
a
Doru Anastasiu Popescu, Pites , ti