洛谷5025 [SNOI2017]炸弹
LuoguLOJ分析最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。写起来还是很休闲的代码`// ========================...
标签 tarjan 下的文章
- 首页
- tarjan
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$ 是这个环的顶端。我们把这个环找出来单独考虑。先考虑怎么用环上的点更新答案。要求的实际上是 $\...
BZOJ4316 小C的独立集
BZOJ分析我们在 $\mathrm{tarjan}$ 的同时跑 $\mathrm{dp}$ 。设 $f[i][0/1]$ 表示 $i$ 子树中， $i$ 选/不选的最大独立集大小。如果一条边是桥，那么和树上独立集一样的转移。否则，这条边在环上，那么暂时先不转移。假设我们现在正在 $u$ 点，$v$ 点已经访问过了，那么 $v$ 是这个环的顶端， $u$ 是这个环的底端。这时我们可以通过跳父...
洛谷3825 [NOI2017]游戏
LuoguBZOJLOJUOJ分析搜索+$\mathrm{2-SAT}$ 。先考虑没有x怎么做。每张地图有两种选择，有一堆限制，这就是个裸的 $\mathrm{2-SAT}$ 。于是随便就有 $45$ 分了...注意到 $d$ 很小，最大只有 $8$ 。于是可以爆搜每张 x 地图选了什么，然后 $\mathrm{check}$ 即可。时间复杂度 $O(3^d(n+m))$ ，如果常数优秀应该...
洛谷3209 [HNOI2010]平面图判定
LuoguBZOJ分析$\mathrm{2-SAT}$ 。首先把环抽出来，那么还会剩下很多边。考虑两条有交点的边（这里的 $(1,4)$ 和 $(2,5)$ ）：显然只能一条不变（放在环里面），一条从外面绕一下（放在环外面）。于是就可以上 $\mathrm{2-SAT}$ 了。对于两条有交点的边 $i$ 和 $j$ ，连以下 $4$ 条边：$i\to j+m$ ，表示 $i$ 在里面 $j$...
洛谷4171 [JSOI2010]满汉全席
LuoguBZOJ分析很裸的 $\mathrm{2-SAT}$ 。把 $i$ 拆成 $i$ 和 $i+n$ ，分别表示汉式和满式。对于每个要求 $(a_c,b_d)$ ，这样子连边：如果 $a$ 为 $m$ ， $b$ 为 $m$ ，那么 $c$ 向 $d+n$ 连边，$d$ 向 $c+n$ 连边。如果 $a$ 为 $m$ ， $b$ 为 $h$ ，那么 $c$ 向 $d$ 连边， $d+n...