【CF Round #545】C. Museums Tour

Description:


一张\(n\)个点\(m\)条边的有向图,每个点有一个博物馆,一个星期有\(d\)天,每个博物馆在一周中某几天固定开放,初始时在\(1\)号点,星期\(1\),如果当天你所在的点的博物馆开放,则可以进入参观,每天结束时,可以沿着有向边进入相邻的点。

问最多可以参观多少个不同的博物馆。

\(n,m\leq 10^5, d\leq 50\)

Examples:


input1 output1
4 5 3
3 1
1 2
2 4
4 1
2 3
011
110
111
001
3
input2 output2
3 3 7
1 2
1 3
2 3
1111111
0000000
0111111
2

Solution:


首先拆点,将每个点拆成\(d\)个,代表不同星期,原图中的每条边改为\(d\)条。

这样用tarjan缩点后剩下的DAG中每个SCC中的点都可以互相到达,于是统计每个SCC中开放的不同的博物馆的数量。之后在DAG上DP。

会有个问题就是可能同一个点在不同SCC中重复计算了。但仔细思考后发现不会有这样的情况。原因如下:

假设第\(i\)个点星期\(j\)代表的点为\((i, j)\),如果存在路径\((i, j) \rightarrow (i, j’) (j \neq j’) \),则设\(\Delta T=(j’-j+d)\%d \),必同时存在路径\((i, k) \rightarrow (i, (k + \Delta T)\%d) \), \((k\in (0, d – 1))\),因此,若\( j’ + k\Delta T \equiv j (\mathbf {mod}\;d)\)有正整数解,则同时存在路径\((i,j’) \rightarrow (i, j)\),又因为\(j + \Delta T \equiv j’ (\mathbf {mod}\;d)\),带入原方程可化为\((k + 1)\Delta T \equiv 0 (\mathbf {mod} \; d)\), 显然存在正整数解\(k=2d-1\),因此\((i,j),(i,j’)\),在同一个SCC中。

所以DAG上直接DP就可以了。

Code:

 


3 评论

  1. Berberis vulgaris es un medicamento homeopГЎtico obtenido a partir del agracejo, un arbusto de la familia de las berberidГЎceas que tiene la particularidad
    vena cava
    Cancer de riГ±Гіn contractura lumbar sintomas

  2. Pensacola Beach, Florida, es uno de los destinos mГЎs populares de la Costa del Golfo en el noroeste de Florida. Alineada con lujosos condominios frente
    social security medicare
    Recursos disponibles para los residentes del condado de Fremont durante el cierre del gobierno Canon City Daily registra mi cuenta de seguridad social Obtenga una nueva tarjeta de seguridad social, nГєmero de telГ©fono de seguridad social, cambio de nombre de seguridad social, oficina de administraciГіn de seguridad social, oficinas de seguridad social

发表评论

电子邮件地址不会被公开。 必填项已用*标注