SCC 的动态维护
stripe_python · · 算法·理论
省流:离线分治求出每条边的闭合时刻,对时间轴扫描线,将 SCC 等效为无向图连通块。
QOJ2214 Link Cut Digraph
维护一张
n 个点初始无边的有向图,进行m 次加边,每次操作后求出强连通点对数。
:::::success[题解]
设
对时间轴升序扫描,若
问题转化为求每条边
对分治区间上的边
- 若
f(e) \le m 且T(e) >m ,边e 不满足f(e) \ge T(e) 故直接删去。 - 若
f(e) \le m 且T(e) \le m ,边e 在左侧[l,m] 正常,在右侧(m,r] 等效为u \leftrightsquigarrow v 分量的单点。 - 若
f(e) > m 且T(e) >m ,边e 只在右侧(m,r] 可用。 - 若
f(e)>m 且T(e) \le m ,边e 对左侧不改变强连通性,故只对右侧(m,r] 有效。
每条边
注意精细实现,只遍历
总复杂度
:::::
P5163 WD与地图
维护一张
n 个点m 条边的有向图,点有点权a_i ,支持q 次操作:
- 给定
u,v ,删去u \to v 的边。- 给定
u,\delta ,令a_u \gets a_u+\delta 。- 给定
u,k ,求u 所在 SCC 内部前k 大点权和。
:::::success[题解] 时光倒流变为加边。
离线分治求出闭合时刻,对时间轴扫描线,将 SCC 转化为无向图连通块。
使用并查集维护连通块,用权值线段树 / 平衡树维护连通块内前
| 复杂度 |
|---|
CF1989F Simultaneous Coloring
现有一个
n \times m 的网格,你可以将一列涂黑,或者将一行涂白。每轮可以同时进行
k 次操作,代价为[k>1]k^2 。对于同时受到两类操作影响的格子,颜色可以自由选定。进行
q 次操作,给定(x,y,c) ,增加一条限制,格子(x,y) 必须涂成颜色c 。每次操作后,输出满足所有要求的最小代价。
:::::success[题解]
显然行列至多操作一次。设第
考虑用
分析可得,最优策略一定是对每个 SCC 整体操作,再按缩点后拓扑序依次操作。答案即为所有 SCC 点数平方和。
离线时间轴分治求出每条边的闭合时刻
视
:::::