Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | hamilton.in, hamilton.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Ciclu hamiltonian de cost minim
Se dă un graf neorientat simplu cu N vârfuri şi M muchii, fiecare muchie având asociat un cost. Un ciclu al acestui graf se numeşte hamiltonian dacă conţine fiecare nod din graf exact o singură dată. Un graf care conţine un astfel de ciclu se numeşte graf hamiltonian. Costul unui ciclu este egal cu suma muchiilor aflate pe ciclu.
Cerinta
Fiind dat un graf neorientat simplu cu costuri pe muchii, să se verifice dacă acesta este hamiltonian. In caz afirmativ, să se determine ciclul hamiltonian de cost minim.
Date de intrare
Pe prima linie a fişierului de intrare hamilton.in se afla două numere întregi N si M. Pe fiecare din următoarele M linii se găseşte un triplet de forma x y c cu semnificaţia că există muchie între vârfurile x şi y având costul c.
Date de ieşire
Pe prima linie a fişierului de ieşire hamilton.out se va afla costul ciclului cerut. Următoarea linie va conţine N numere x1 x2 ... xn cu proprietatea că (x1 x2) (x2 x3) ... (xN-1 xN) (xN x1) reprezintă un ciclu hamiltonian de cost minim. În cazul în care graful nu este hamiltonian, atunci în fişierul de ieşire se va afişa -1.
Restricţii
- 1 ≤ N ≤ 16
- 1 ≤ M ≤ N*(N-1)/2
- Costurile muchiilor sunt numere întregi cuprinse in intervalul [1, 1 000 000].
Exemplu
| hamilton.in | hamilton.out |
|---|---|
| 5 6 1 2 3 1 3 2 1 5 5 2 3 4 3 4 7 4 5 6 | 25 |
Explicaţie
...
Indicaţii de rezolvare
Aplicaţii
Pentru a vă consolida cunoştinţele privind algoritmul prezentat in această problemă, vă recomandăm să rezolvaţi următoarele probleme:
