Problem
Besi está ubicado en una red de N (2≤N≤10
5) vértices etiquetados como 1…N y 2N portales etiquetados como 1…2N. Cada portal conecta dos vértices diferentes u y v (u≠v). Un conjunto de portales puede conectar algún par de vértices.
Cada vértice v es adyacente a cuatro portales diferentes. La lista de portales de v viene dada por pv=[p
v,1,p
v,2,p
v,3,p< sub>v,4].
Su posición actual se puede representar mediante un par ordenado (vértice actual, portal actual); es decir, un par (v,p
v,i) donde 1≤v≤N y 1≤i≤4. Puede usar una de las siguientes operaciones para cambiar su posición actual:
Cambie el vértice actual moviéndose a través del portal actual.
Cambiar portal actual. En cada vértice, los dos primeros portales de la lista están emparejados y los dos últimos portales de la lista también están emparejados. Entonces, si su estado actual es (v,p
v,2), entonces puede cambiar para usar el portal (v,p
v,1) y viceversa. Del mismo modo, si su posición actual es (v,p
v,3), puede cambiar al portal (v,p
v,4) y volver. no se permite ningún otro cambio (por ejemplo, no puede cambiar del portal pv,2 al portal) p
v,4).
Hay 4N estados diferentes en total. Desafortunadamente, puede que no sea posible llegar a cualquier estado desde cualquier estado mediante una secuencia de operaciones dadas. Por lo tanto, por el costo de cv (1≤c
v≤1000) lunas, puede reorganizar la lista de portales adyacentes a v, en el orden que desee. Después de eso, los dos primeros portales de la lista se combinan en un par y los dos últimos portales en otro par.
Por ejemplo, si reorganiza los portales de v en el orden [p
v,3,p
v,1,p
v,2, p
v,4], Esto significa. ¿Qué pasa si estás en la parte superior v,
Si está en el portal p
v,1, puede cambiar al portal p
v,3 y regresar
Si está en el portal p
v,2, puede cambiar al portal p
v,4 y regresar
Ahora no puede cambiar del portal p
v,1 a p
v,2, o del portal p
v,3 al portal p
v,4 y viceversa.
Calcule el número mínimo de lunas requeridas para modificar la red de tal manera que cada estado sea accesible desde cada estado. Se garantiza que los datos de prueba se construyan de tal manera que haya al menos una forma de modificar la red de esta manera.
Entrada:
La primera línea contiene N.
Cada una de las siguientes N líneas describe un vértice. La cadena v+1 contiene 5 enteros separados por espacios c
v,p
v,1,p
v,2,p
v ,3,p
v,4.
Se garantiza que para cada v todos p
v,1,p
v,2,p
v,3,p
v, 4 son distintos, y cada portal aparece en las listas de exactamente dos vértices.
Salida:
Una línea contiene la cantidad mínima de lunas requeridas para modificar la red para que cada estado sea accesible desde otro estado.
Ejemplos
| # |
Entrada |
Salida |
Explicación |
| 1 |
5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5 |
13 |
Es suficiente intercambiar listas de vértices 1 y 4. Esto requiere c1+c4=13 muns. Las permutaciones son: p1=[1,9,4,8] y p4=[7,4,6,3]. |