Cómo resolver esta pregunta en Codeforces

Answer 1

Cada nodo [math] i [/ math] debe tener un puesto de control o debe estar protegido por otro puesto de control construido en el nodo [math] j [/ math] y debe haber una ruta desde [math] i [/ matemática] a [matemática] j [/ matemática] y [matemática] j [/ matemática] a [matemática] i [/ matemática].

Esto se parece mucho al problema del componente Fuertemente conectado. Básicamente, su gráfico de entrada se dividirá en una lista de componentes fuertemente conectados. Para entender por qué, necesita leer sobre ese tema. En resumen, para tres nodos [matemática] a, b, c [/ matemática], si [matemática] a [/ matemática] y [matemática] b [/ matemática] están en un componente fuertemente conectado y [matemática] b [/ math] y [math] c [/ math] están en un componente fuertemente conectado, entonces los tres están en el mismo componente fuertemente conectado. Por lo tanto, obtienes un montón de componentes disjuntos fuertemente conectados. Llamémoslos [math] \ {g_1, g_2, \ cdots g_n \} [/ math]. Hay un algoritmo de tiempo lineal (algoritmo de Kosaraju) para hacer esto.

Ahora, para cada componente, lo natural es elegir construir el puesto de control en el nodo con el costo mínimo. Puede encontrar la respuesta a la primera pregunta de esta manera. Para la segunda parte, si existen dos o más nodos con el mismo costo mínimo, los eliges y, por lo tanto, tu solución será diferente. Entonces, si deja que [math] c_1 [/ math] sea el número de nodos con un costo mínimo de [math] g_1 [/ math] y lo mismo para el resto, la respuesta a la segunda parte es [math] \ prod_ {i = 1} ^ n c_i. [/matemáticas]