Restricciones coloreadas#13096
Se da un grafo no dirigido con vértices y aristas.
Cada vértice tiene un bit inicial a_i, igual a o , y un costo no negativo w_i para cambiarlo.
Puedes cambiar los bits de los vértices. Si el bit final del vértice difiere de su bit inicial, debes pagar w_i.
Cada arista tiene un color de a y un número , igual a o .
Una arista entre los vértices y impone la restricción x_u \oplus x_v=b, donde x_u y x_v son los bits finales de los vértices correspondientes, y denota la operación XOR bit a bit.
Para cada color , realiza de forma independiente los siguientes pasos:
Elimina del grafo todas las aristas de color .
Elige los bits finales de todos los vértices de modo que se cumpla la restricción de cada arista restante.
Minimiza el costo total de cambiar los bits.
Halla el costo mínimo para cada color por separado. Si es imposible satisfacer todas las restricciones restantes, la respuesta para ese color es .
Todos los casos son independientes: antes de eliminar el siguiente color, el grafo y los bits iniciales de los vértices se restauran a su estado original.
La primera línea contiene tres enteros , y (1 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5) — la cantidad de vértices, aristas y colores.
La segunda línea contiene una cadena binaria de longitud , donde a_i es el bit inicial del vértice .
La tercera línea contiene enteros w_1,w_2,\ldots,w_n (0 \leq w_i \leq 10^9) — los costos de cambiar los bits.
Cada una de las siguientes líneas contiene cuatro enteros , , y (1 \leq u,v \leq n, b \in \{0,1\}, 1 \leq c \leq k). Esto describe una arista de color entre los vértices y que impone la restricción x_u \oplus x_v=b.
El grafo puede contener aristas paralelas y bucles. Algunos colores pueden no aparecer entre las aristas.
Imprime enteros.
El entero en la posición debe ser el costo mínimo después de eliminar todas las aristas de color , o si no es posible satisfacer todas las restricciones restantes.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo, después de eliminar las aristas de los colores , y , se pueden elegir los bits finales 100, 110 y 000, respectivamente. Los costos mínimos son 5+2=7, y .
En el segundo ejemplo, al eliminar el color quedan dos restricciones idénticas x_1=x_2. Basta con cambiar el bit del primer vértice a un costo de . Al eliminar el color , o el color , que no aparece en el grafo, queda un bucle que exige x_1 \oplus x_1=1, lo cual es imposible.
En el tercer ejemplo no hay aristas. Para cada color se pueden dejar todos los bits iniciales sin cambios, por lo que ambas respuestas son .
puntos — k=1.
puntos — n \leq 16, m \leq 30, k \leq 10.
puntos — n,m,k \leq 2000.
puntos — k \leq 20.
puntos — b=0 para cada arista.
puntos — w_i=0 para cada vértice.
puntos — sin restricciones adicionales.