News | Introduction | Contributors | Problems | Results | Solutions | Links

akyu | cirno | furan | hatate | inaba | kaguya | marisa | pache | reimu | sakuya | shiki | youmu | yuyuko

kaguy. Attack the NEET Princess

ZOJ3378. 推倒NEET姫

source 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的任意一条最短路，那么那些不是必经之路的桥一定不在这个最短路中，所以所有在最短路中的桥就是所求答案。