Alguns camins Hamiltonians P90225


Statement
 

pdf   zip

thehtml

Suposeu un graf dirigit amb n vèrtexs i tots els n(n − 1) arcs possibles, alguns dels quals estan pintats. Quant camins Hamiltonians hi ha que comencin en el vèrtex 0, acabin en el vèrtex n−1, i no passin per dos arcs pintats consecutius?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, seguit d’una matriu n × n on a la posició (i, j) hi ha el color de l’arc que va del vèrtex i fins al j. Un u indica que l’arc està pintat, i un zero que no. La diagonal (que és inútil) només té zeros. Suposeu n ≥ 2.

Sortida

Per a cada cas, escriviu quantes permutacions dels n vèrtexs comencen en 0, acaben en n − 1, i no tenen tres vèrtexs consecutius x, y i z tals que els dos arcs xy i yz estiguin pintats. Els jocs de proves són tals que la resposta és més petita que 106.

Public test cases
  • Input

    2
    0 1
    1 0
    
    3
    0 1 1
    1 0 0
    1 1 0
    
    3
    0 1 0
    0 0 1
    0 0 0
    
    5
    0 1 0 0 0
    1 0 1 0 0
    0 0 0 0 1
    1 0 0 0 1
    0 1 0 0 0
    

    Output

    1
    1
    0
    4
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++