Phecda_

未归档

/ 注册

全部文章 / 未归档（共4篇）

LuoGu P2783 有机化学之神偶尔会做作弊

题目传送门人生第一道黑题呢,虽然这题是黑题中的水题并且我调了一整节课,但是我还是很兴奋啊.毕竟人生第一道黑题啊这个题根据题意，先把整个图进行tarjan缩点，建出一棵树，对于每一组询问，两点之间的距离+1就是答案，求出他们的LCA，两点到LCA的距离之和就是两点之间的距离然后....LCA我采...

tarjan缩点 SCC 树链剖分

2018-09-11

0 466

LuoGu P2002 消息扩散

题目传送门这个题其实就是tarjan缩点的板子题对吧....至少我是这么想的首先这是个有向图，对于一个有向图，我们肯定要考虑环的存在与否，恰好这个题又是让我们找出最少的点，使得这几个点能够走遍全图那么，显然，对于每一个强连通分量，我们看做一个点即可（因为强连通分量中每两个点之间一定能从一个点到...

tarjan缩点 SCC 并查集最小环

2018-09-14

0 351

LuoGu P2835 刻录光盘

题目传送门这个题和消息扩散那个题，一模一样啊除了数据范围小一点，搜索能过之外，没啥区别但是我写WA了QwQ不知道为什么和消息扩散的代码fc/diff了半天也没找出来哪不一样换了输入就过了反正QwQ #include <iostream> #include <cstdli...

tarjan缩点 SCC

2018-09-14

0 354

LuoGu P2863 [USACO06JAN]牛的舞会The Cow Prom

题目传送门这个题还是个缩点的板子题...... 答案就是size大于1的强连通分量的个数加一个size来统计就好了 #include <iostream> #include <cstdlib> #include <cstdio> using namespa...

tarjan缩点 SCC

2018-09-14

0 322