【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:

 


发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据