摘要：
树状数组（Binary Indexed Tree, BIT，也称 Fenwick Tree）是算法竞赛中极其常用的数据结构。它的核心优势在于：代码短小精悍、常数极小、内存占用少。 虽然它的功能是线段树的子集，但在处理“动态前缀和”相关问题时，BIT 通常是首选。 来自董晓算法，对两个关键函数原理的图 阅读全文
posted @ 2026-02-23 23:13
tingshuo2917
阅读(2)
评论(0)
推荐(0)
摘要：
强连通分量 前置知识：DAG基础。比如出度为 \(0\) 和入度为 \(0\) 的点的性质及影响，拓扑排序及其性质 需要掌握：缩点 G001 强连通分量 Tarjan算法 P2812 USACO Network of Schools 校园网络 G002 强连通分量 Tarjan算法 CF999E R 阅读全文
posted @ 2026-02-23 21:35
tingshuo2917
阅读(2)
评论(0)
推荐(0)
摘要：
P3387 【模版】缩点 - 洛谷 给定一个有向图，每个点都有一个权值，允许多次经过一条边或者一个点但权值只计算一次。求一条权值之和最大的路径。 很明显的拓扑排序最长路问题，考虑缩点后进行 DP 。一般的方法为 缩点后得到 DAG ，在新的 DAG 里进行拓扑排序。 在拓扑排序的过程中更新状态转移方 阅读全文
posted @ 2026-02-23 21:29
tingshuo2917
阅读(1)
评论(0)
推荐(0)
摘要：
CF999E Reachability from the Capital - CodeForces 给定一个有向图和一个节点 \(s\) ，问最少加多少条边可以使 \(s\) 可以到达图中所有的点（ \(s\) 可以到达自身） 考虑缩点，缩点后源点一定被无法到达，所以我们需要统计源点的个数。 特判， 阅读全文
posted @ 2026-02-23 17:31
tingshuo2917
阅读(4)
评论(0)
推荐(0)
摘要：
P2812 校园网络 [USACO]Network of Schools - 洛谷 给定一个有向图， \(A \rarr B\) 表示 \(A\) 可以给 \(B\) 发送软件。 问：最少需要给多少学校发送软件可以让所有学校收到 问：最少加几条边，可以给任意一所学校发送软件使全图可以收到 在有向图中 阅读全文
posted @ 2026-02-23 16:32
tingshuo2917
阅读(1)
评论(0)
推荐(0)
浙公网安备 33010602011771号