TH911 Blog

「光阴不可测，岁月亦无歌。」

无向图 Tarjan 求割点详解

例题：洛谷P3388

例题链接 割点 所谓割点，就是连通图中的某一个点满足删除该点后，原图不再连通。 如图中的 $2,4$ 就是一个割点。 但需要注意的是，割点不一定在环上，比如： 图中的 $2$ 就是割点。 不过存在特殊情况： 该图没有割点，无论去掉 $1$ 还是 $2$，最后都会剩下一个节点。 关于“割点”不同的定义 如同平衡树中的“左旋...

Posted by TH911 on January 23, 2025

题解：最短路计数

洛谷P1144

题目传送门 题意分析 因为是无向无权图，因此可以通过 BFS 求最短路。 BFS 找到即最优，因此找的时候递推即可。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ...

Posted by TH911 on January 23, 2025

无向图 Tarjan 边双连通分量详解

例题：洛谷P8436

例题链接 只有无向图有边双连通分量 有向图没有“边双连通分量”这个概念，只有“连通分量”、“强连通分量”和“弱连通分量”。 有向图见强连通分量。 边双连通分量 众所周知，在有向图中，存在强连通分量，强连通分量中的任意两点是连通的。 而在无向图中，同样存在边双连通分量。 边双连通 若一个无向...

Posted by TH911 on January 23, 2025

题解：[HAOI2006] 受欢迎的牛 G

题解：[USACO03FALL] 受欢迎的牛 G | 洛谷P2341

题目传送门 题意分析 给定 $n$ 个点，$m$ 条有向边，求有多少个点能够到达其他全部的点。 题目给出的类似于“奶牛 $A$ 喜欢奶牛 $B$”，我们可以从点 $B$ 向点 $A$ 连边，表示“$B$ 被 $A$ 喜欢”。 随后我们只需要看是否能够找到一个点，使其能够抵达所有的点即可。 但是会有环，因此我们可以用 Tarjan 缩点 来处理掉环，使得原图成为一个有...

Posted by TH911 on January 23, 2025

有向图 Tarjan 求强连通分量详解

有向图 Tarjan 缩点 | 例题：洛谷P3387

$\text{Upd on 2025/11/26}$：部分内容重写。好在没有 KMP 那么抽象。优化代码。 只有有向图有强连通分量 无向图没有“强连通分量”这个概念，只有“连通块”。 无向图请看边双连通分量和点双连通分量。 引入 luogu P3387 给定一个 $n$ 个点 $m$...

Posted by TH911 on January 23, 2025

题解：[USACO10MAR] Great Cow Gathering G

洛谷P2986

题目传送门 树形 DP 换根树形 DP。 令 $dis_x$ 表示节点 $x$ 的子树内不方便程度的和。 显然，$dis_x$ 会因为根节点的不同而不同，我们考虑如何转换。 令 $dp_x$ 表示以 $x$ 为根节点时，不方便程度之和。 原来的 $dis_x$ 则是在以 $1$ 为根节点的条件下求得的。 则： \[dp_1=dis_1\] 对于节点 $x$ 的子节点...

Posted by TH911 on January 22, 2025

题解：[POI2008] STA-Station

洛谷P3478 | 换根 DP

题目传送门 树形 DP 依然是树形 DP。 首先，在根节点确定的情况下，深度之和显然可以 $\mathcal O(n)$ 求。 但是现在根节点不确定，因此我们需要 $\mathcal O(n)$ 来枚举根节点。 然而这样时间复杂度就来到了 $\mathcal O\left(n^2\right)$，考虑到 $1\leq n\leq 10^6$，无法通过此题。 如图： ...

Posted by TH911 on January 22, 2025

题解：[USACO06NOV] Round Numbers S

洛谷P6218

题目传送门 题意分析 求 $[l,r]$ 中有多少个整数满足其二进制中，$0$ 的个数大于等于 $1$ 的个数。 注意一个数的二进制不包括其前导 $0$。例如对于 $9$，其二进制仅仅是 $1001$。 分块打表 考虑到 $1\leq l\leq r\leq 2\times 10^9$，并不是很大，考虑分块打表。 计算机一秒内能够处理的数据规模约为 $4\times 10...

Posted by TH911 on January 22, 2025

题解：叶子的染色

洛谷P3155

题目传送门 题意分析 注意 无色节点不是白色节点。 给定一棵 $m$ 个节点的无根树并指定 $n$ 个叶子节点。 规定根节点到叶子节点 $i$ 的路径上深度最大的有色节点的颜色为 $c_i$，保证根节点的度数大于 $1$。 求最少染色节点数。 树形 DP 状态设计 暂不考虑因为根节点不同而产生的影响，后文会证明根节点的不...

Posted by TH911 on January 22, 2025

题解：消息传递

洛谷P2018

题目传送门 加强版数据包 加强版数据包满足 $2\leq n\leq 200000$，需要使用 $\mathcal O\left(n\log n\right)$ 做法。 题意分析 给定一棵无根树，最开始花费 $1$ 时刻可以选择一个节点告知一条消息，每一个时刻每一个已知消息的节点都可以告知其他一个节点，求消息传遍整棵树的最短时间和最开始能选择的节点有哪些。 $\ma...

Posted by TH911 on January 22, 2025

FEATURED TAGS
树状数组 题解 省选/NOI− 提高+/省选− DP 基础算法 普及+/提高 数学 线段树 贪心 普及/提高− 组合数学 字符串 未完 二分 图论 平衡树 数论 树形 DP Tarjan 位运算 搜索 Trie 二分答案 状态压缩 无聊时候的一点思考 最短路 FHQ Treap NOI/NOI+/CTSC 前端 前缀和 树链剖分
ABOUT ME

要做一个优秀的 OIER

FRIENDS