

kaguya. Attack the NEET Princess
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的任意一条最短路,那么那些不是必经之路的桥一定不在这个最短路中,所以所有在最短路中的桥就是所求答案。
©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/
watashi同学,你发我个 数据好不?
同学,不需要数据乐。。。。55555555555555傻傻的AC乐。
据说套费用流模板可以过。把一条边拆成两条,其中一条费用为0,一条费用为1,容量都是1,然后搞两次增广……
这个太神了,戴牛的方法?费用流苦手
对。戴神好像是个图论题都能用网络流的模板过……
对于网络流 这题的点数和边数是不是太大了?
请问测试数据公布么?我一直wa,很诡异。。。
不公布……
可以给两个case
2 2
0 1
0 1
3 2
0 2
2 1
很显然的答案是
0
1
0
很显然的答案是
0
1
0
能想到的数据应该都过了 包括重边,自环。。。
你的求桥部分能不能过ZOJ2588 Burning Bridges这道题?
能过2588,但是过不了这道题。。请问能求测试数据对拍一下么 方便的话请发到abilitytao@gmail.com 非常感谢啊
桥的数目为0的时候,第二行要输出一个空行的,不知道ls错是不是这个原因?
其实这道题不用求桥也可以啦。
只要一条边在环上,那就不可能是要找的边。
随便找一条S->T的路径,其上不在任何环的边就是所求边了。
这也可以O(N)实现的。
不在任何环的边其实就是桥吧?
我想问下:如果按tarjan算法求连通分量必然要把每条边增加两条.可是如果增加两条的话.如:a-b
那么a b必然成为一个连通分量了.怎么解决这个问题
不求连通分量啊,dfs求割边就可以了,本来就是做无向图的