CF487E Tourists
CodeforcesLuogu分析可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修...
标签 tarjan 下的文章
- 首页
- tarjan
洛谷1173 [NOI2016]网格
LuoguLOJ分析首先发现答案只可能是 $-1,0,1,2$ 中的一个：当图本就不连通时答案为 $0$，当图存在割点时答案为 $1$，当 $nm-c<2$ 或 $nm-c=2$ 且剩下两只跳蚤相邻时答案为 $-1$，否则答案为 $2$。然而把整张图都建出来显然是不现实的。不难想到只把每只蛐蛐周围一圈跳蚤拿出来建图，但这样会有问题：.** .*# .**此时第二行第二列的 * 在新图中...
洛谷3825 [NOI2017]游戏
LuoguLOJ分析没有 x 时显然是 2-SAT。将每张图拆成两个点表示能填的两种赛车。为了方便，设 $(i,a)$ 表示 $i$ 填 $a$ 所对应的点，$(i,\neg a)$ 表示 $i$ 不填 $a$（即填另一种赛车）对应的点。对于每个条件 $(i,a,j,b)$如果 $s_i\neq a$，忽略。如果 $s_j\neq b$，连边 $(i,a)\to (i,\neg a)$，表示...
LOJ3280 「JOISC 2020 Day4」首都城市
LOJ分析考虑建一个图，即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点，则从 $i$ 向 $j$ 连一条边。那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通，则必须把 $u,v$ 合并。考虑一个强连通分量，显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并，因此一个强连通分量需要合并 $sz-1$ 次。于是我们缩点并将 $sz-1$ ...
洛谷5025 [SNOI2017]炸弹
LuoguLOJ分析最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。写起来还是很休闲的代码`// ========================...
CF894E Ralph and Mushrooms
CodeforcesLuogu分析显然一个强连通分量内的所有边都可以无限走，因此可以考虑缩点。缩点后，每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和，连接强连通分量的边的权值设为边上的蘑菇数，然后 DP 求最长路即可。考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$，那么代码// =============================...
ARC069F Flags
AtCoderLuogu分析容易想到二分答案，那么只要判定能不能找到一组方案使得所有点的距离都 $\geq mid$ 即可。考虑 2-SAT 。如果某面旗帜选了某个位置的话，会有一些旗帜只能选某个位置。于是 $O(n^2)$ 连边后 tarjan 即可。这个算法的瓶颈在于连边太慢了，考虑优化。首先，把所有位置都拿出来排个序，那么一个点一定会向一段区间内的点的反点连边，而这个区间是可以二分出来...
CF1215F Radio Stations
CodeforcesLuogu分析很神仙的 2-SAT 。设表示第 $i$ 个电台启用的点为 $yes(i)$ ，表示第 $i$ 个电台不启用的点为 $no_i$ 。先考虑一下 $u$ 和 $v$ 至少启用一个怎么连边。连 $no(u)\to yes(v)$ 和 $no(v)\to yes(u)$ 即可。再考虑一下 $u$ 和 $v$ 不能同时启用怎么连边。连 $yes(u)\to no(v...
洛谷1407 [国家集训队]稳定婚姻
LuoguBZOJ分析感觉这题好妙啊...把所有男性设成黑点，女性设成白点，所有婚姻关系和情侣关系看成边。那么可以发现，如果一对婚姻在一个黑白点交错、婚姻关系和情侣关系交错的环上，那么这对婚姻是不安全的。考虑把所有边定向：婚姻关系男向女连边、情侣关系女向男连边。那么可以发现，如果一对婚姻的男女方在同一个强连通分量里，那么这对婚姻是不安全的。代码// =====================...
洛谷4244 [SHOI2008]仙人掌图
LuoguBZOJ分析和仙人掌最大独立集类似，不过难一些。设 $f[i]$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。如果当前边是桥，直接转移，同时更新 $ans$ 。否则当前边在环上，先不处理。假设我们现在在 $u$ ， $v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。我们把这个环找出来单独考虑。先考虑怎么用环上的点更新答案。要求的实际上是 $\...