Graf blau-vermell òptim P71017


Statement
 

pdf   zip

html

Donat un graf no dirigit, n’heu de pintar cada vèrtex de blau o de vermell. Pintar de blau costa 1, i pintar de vermell costa 2. L’objectiu és minimitzar el cost total de pintar el graf. Només hi ha una restricció: Cada vèrtex només pot tenir, com a màxim, un vèrtex adjacent del mateix color que ell mateix.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n, el nombre d’arestes m, i les m arestes x y, amb x ≠ y. Els vèrtexs es numeren a partir de 0. No hi ha arestes repetides. Podeu assumir 1 ≤ n ≤ 40.

Sortida

Escriviu el cost mínim de pintar cada graf. Si un graf no es pot pintar, escriviu “NO”.

Puntuació

La solució esperada és un backtracking raonablement optimitzat. El jutge us donarà una estimació de la nota màxima que podeu treure (5, 8 o 10) en funció de l’eficiència del vostre codi. En qualsevol cas, tots els últims enviaments s’avaluaran manualment, inclosos els que rebin 0 punts automàtics.

Public test cases

  • Input

    2 0
5 4  0 1  1 2  2 3  3 4
8 7  3 7  7 4  0 6  6 1  7 6  2 6  5 7
5 8  0 1  0 2  0 3  0 4  1 2  2 3  3 4  4 1
4 4  0 1  1 2  2 3  3 0

    Output

    2
6
10
NO
6
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++