Tots els cicles hamiltonians P16553


Statement
 

pdf   zip

thehtml

Donat un graf dirigit amb costs positius als arcs, escriviu tots els camins que surten del primer vèrtex, acaben al primer vèrtex, i passen per tots els altres vèrtexs exactament un cop. A més, escriviu el cost de cadascun d’aquests cicles.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n, seguit de n files amb n nombres cadascuna. El nombre j-èsim de la fila i-èsima indica el cost de l’arc que va del vèrtex i al vèrtex j (els vèrtexs es numeren de 0 a n − 1). Un cost igual a zero indica que l’arc no existeix (la diagonal només té zeros). Poseu suposar que n és “petita” i com a mínim 2, i que el cost de cada cicle cap en un enter.

Sortida

Escriviu, en ordre lexicogràfic, tots els cicles de longitud n que surten i acaben en el vèrtex 0 sense repetir vèrtexs, i el cost de cada cicle. Escriviu una línia amb 20 guions al final de cada cas.

Public test cases
  • Input

    2
    0 5
    7 0
    
    3
    0 1 2
    3 0 4
    5 6 0
    
    4
    0 1 1 1
    1 0 1 1
    1 1 0 1
    1 1 1 0
    
    5
     0  0 20 30  0
     0  0 10 50 60
    90 80  0  0 70
    40  0 25  0 95
    15 10 75 35  0
    

    Output

    0 1 0 (12)
    --------------------
    0 1 2 0 (10)
    0 2 1 0 (11)
    --------------------
    0 1 2 3 0 (4)
    0 1 3 2 0 (4)
    0 2 1 3 0 (4)
    0 2 3 1 0 (4)
    0 3 1 2 0 (4)
    0 3 2 1 0 (4)
    --------------------
    0 2 1 3 4 0 (260)
    0 2 1 4 3 0 (235)
    0 2 4 1 3 0 (190)
    0 3 2 1 4 0 (210)
    0 3 4 1 2 0 (235)
    --------------------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++