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

 


18 评论

  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

  3. 萨姆拉酒店 е­џд№° – 2星级酒店. 2星级优雅的Hotel SamrajжЏђдѕ›24е°Џж—¶жњЌеЉЎеЏ°жњЌеЉЎпјЊйљЏеЏ«дёЉй—ЁеЊ»з”џжњЌеЉЎе’ЊжЉҐе€ЉжњЌеЉЎгЂ‚
    What is reflexology good for

  4. No.0001 – Login – Dataпјљ2005/10/18 Last Updateпјљ2005/11/07 еђЌ е‰Ќпјљ гЃѕгЃЎг‚ѓ: жЂ§ 別: 女: гѓ¬гѓ™гѓ«пјљ 37: タイプ: スピリチュアリスト
    Haldol in elderly

  5. Feminist theory is one of the major contemporary sociological theories, which analyzes the status of women and men in society with the purpose of using that knowledge to better womens lives. Feminist theory is most concerned with giving a voice to women and highlighting the various ways women have contributed to society.
    anxiety meaning in hindi symptoms

  6. Other more rare causes of abdominal muscle spasms are diverticulitis, intussusception, hernia, cholecystitis, and bowel obstruction. Treatment for Abdominal Muscle Spasms After discovering the cause of your abdominal muscle spasms, you must seek treatment options.
    north korea

  7. Hello! kkeevviinnn.com

    We suggesting

    Sending your business proposition through the feedback form which can be found on the sites in the Communication partition. Contact form are filled in by our program and the captcha is solved. The superiority of this method is that messages sent through feedback forms are whitelisted. This method improve the chances that your message will be read.

    Our database contains more than 25 million sites around the world to which we can send your message.

    The cost of one million messages 49 USD

    FREE TEST mailing of 50,000 messages to any country of your choice.

    This message is automatically generated to use our contacts for communication.

    Contact us.
    Telegram – @FeedbackFormEU
    Skype FeedbackForm2019
    Email – FeedbackForm@make-success.com
    WhatsApp – +44 7598 509161

发表评论

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