kaguya. Attack the NEET Princess

kaguy. Attack the NEET Princess

ZOJ3378. 推倒NEET姫

downloadsource code (ZOJ3378.cpp) [图论(graph), 连通性(connectivity), 割边/桥(cut-edge/bridge), Tarjan]

以“辉红”(辉夜×妹红)为主题的图论题,是我在Contest 11 by ACFun救急凌晨临时出的一套题,那天的事记在了这里。本来想找一个妹红埋伏辉夜的配图,不过没有找到合适的,于是用了这张幼稚园版的。这张也不错,而且師匠和先生都在,还有受兔和腹黑兔子。(《东方永夜抄》的剧情捏的是日本的《竹取物语》)

  • 永遠と須臾の罪人/蓬莱山輝夜(ほうらいさん かぐや)
  • 蓬莱の人の形/藤原妹紅(ふじわらのもこう)
  • 月の頭脳/八意永琳(やごころ えいりん)
  • 知識と歴史の半獣/歴史喰い/上白沢慧音(かみしらさわ けいね)

NEET姫和妹红是一对死敌,可对于总是宅在永远亭的家里蹲NEET姫,妹红一直找不到下手机会。但是博丽神社例大祭的举办时间快到了,作为一个死宅,NEET姫一定会去买各种同人◯◯漫画和游戏,于是妹红打算在NEET姫的必经之路上设好埋伏袭击她。题目要求的就是这些必经之路。

题目要求的是必经之路,也就是去掉这条路,那么NEET姫将不可能从永远亭(0)走到博丽神社(n-1)。图论中,如果删掉一条边,图的联通分量数将增加,那么称其为桥或割边。求桥有Tarjan发现的复杂度O(|V|+|E|)的算法。可以参考wiki或黑书。此题要注意处理重边,有重边的边不可能是桥。

于是要求的必经之路一定也是桥,但不是所有的桥都是必经之路。比如4个点,3条边:1–0, 0–3, 3–2的情况,1–0,3–2是桥,但不在从0到3的路径上,只有0–3是必经之路。如何去掉不是答案的桥呢,方法有很多,其实最简单的只要在dfs里稍作修改即可,而我的方法是再求一个0到n-1的任意一条最短路,那么那些不是必经之路的桥一定不在这个最短路中,所以所有在最短路中的桥就是所求答案。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

17 Responses to “kaguya. Attack the NEET Princess”
  1. boat says:

    watashi同学,你发我个 数据好不?

  2. biribiri says:

    据说套费用流模板可以过。把一条边拆成两条,其中一条费用为0,一条费用为1,容量都是1,然后搞两次增广……

  3. cgy4ever says:

    其实这道题不用求桥也可以啦。
    只要一条边在环上,那就不可能是要找的边。
    随便找一条S->T的路径,其上不在任何环的边就是所求边了。
    这也可以O(N)实现的。

  4. proxy says:

    我想问下:如果按tarjan算法求连通分量必然要把每条边增加两条.可是如果增加两条的话.如:a-b
    那么a b必然成为一个连通分量了.怎么解决这个问题

  5.  
Leave a Reply