「做题记录」图论选做
stripe_python · · 算法·理论
P13271 [NOI2025] 机器人
给出一个
n 个点m 条边的有向图。初始时你位于节点1 ,持有一个正整数x=1 ,上界为k 。每轮中可以执行如下操作:
- 若
x<k ,将x \gets x+1 ,代价为v_x ;- 若
x>1 ,将x \gets x-1 ,代价为w_x ;- 记当前位置为
u ,则走到u 的第x 条出边v ,代价为边权。对于每个节点,求出到达此节点的最小代价。
:::::success[题解]
拆点,状态
对
:::::
P9370 [APIO2023] 赛博乐园 / cyberland
给出一个
n 个点m 条边的无向图,边带权。你需要从节点1 走到节点s ,每次行动的代价为边权。到达s 后不可行动。走到一些节点时可以进行至多一次特殊技能,技能类型为
a_i 。a_i=0 可以清空当前累计代价,a_i=2 可以将当前累计代价除以2 ,a_i=1 无技能。保证a_1=a_s=1 。对于除以
2 的操作,你最多只能进行k 次。求出最小代价,精度要求10^{-6} 。
:::::success[题解]
拆点,状态
状态数为
:::::
P15814 [JOI 2014 Final] 蜜袋鼯 / Sugar Glider
给定一张
n 个点m 条边的无向带权图,给定点权a_1 \sim a_n 。你初始位于节点
1 ,持有数字h 。位于节点u 时需保证h \in [0,a_u] ,可花费1 的代价令h \gets h \pm 1 ,或花费w 的代价经u \overset{w}\to {v} 跳到v 并令h \gets h-w ,其中h-w \in [0,a_v] 。求初始状态
(1,h) 到(n,a_n) 的最小代价,或报告无解。
:::::success[题解]
显然可以拆点
考虑堆优化 Dijkstra 的过程。我们声称,最先入堆的
设
堆内记录
:::::
CF2057E2 Another Exercise on Graphs (hard version)
给定
n 个点m 条边的无向连通带权图。进行q 次询问,给定u,v,k ,查询u \leadsto v 路径中第k 大边权的最小值。多测,
\sum n \le 400 ,m \le \binom{n}{2} ,\sum q \le 3 \times 10^5 ,3 秒,1000 MB。
:::::success[题解]
对询问二分答案
按边权从小到大加边,加到
考虑优化,我们添加一个剪枝:将
:::::
P11795 [JOI 2016 Final] 铁路票价 / Train Fare
给定一张
n 个点m 条边的无向连通图,初始所有边权均为1 。进行q 次操作,将某条边的权值改为2 。操作结束后,求1\leadsto u 最短路大于原图的u 点数目。
:::::success[题解]
对于最短路长度不变的点,新的最短路必不经过边权为
建立最短路图,若边
原图边权为
:::::
P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus
给定一张
n 个点m 条边的有向带权图。你可以翻转至多一条边i 的方向,并产生d_i 的代价。操作结束后,你需要从
1 走到n ,再从n 回到1 ,代价为路径边权和。最小化总代价并输出,或报告无解。
:::::success[题解]
建立以
- 若
e \in E(T_1) ,将其翻转后使用朴素 dij 求1 \leadsto n 的最短路。由于T_1 只有n-1 条边,复杂度O(n^3) 。 - 若
e \notin E(T_1) ,则最短路必为1 \leadsto n 或1 \leadsto v\overset{w}\to u \leadsto n 。预处理全源最短路f_{u,v} ,答案为\min(f_{1,n}, f_{1,u}+w+f_{v,n}) 。
对于
总复杂度
:::::
ZR3778 地铁
给定一棵
n 个点的有根树,根节点为1 ,树边权值为a 。再给出m 个点对(u_i,v_i) ,对u_i \leadsto v_i 树链上每个点x 连单向边u_i \overset{2b}\to x 。求
1 号点到每个点的最短路长度。
:::::success[题解]
性质 1 设
性质 2 令
根据上述两个性质,可以得到优化建图方法:
在新图上跑单源最短路即可。边权只有三种,使用三个队列模拟小根堆,复杂度
:::::
P4745 [CERC2017] Gambling Guide
给定一张
n 个点m 条边的无向图。你需要从起点1 走到终点n 。当你位于节点u 时,你可以支付1 的代价并获得一次前往邻接点v 的机会,你可以选择放弃机会。你需要使最终到达终点的概率为
1 ,并最小化期望代价。输出期望值,精度要求10^{-6} 。
:::::success[题解]
记
当我们位于节点
此时
从上面的式子可以看出,为了让
这一过程非常类似 Dijkstra。最优化 DP 在有环图上的转移顺序正是最短路,因此给出如下流程:
- 用一个优先队列维护
(u,f_u) 二元组,初始加入(n,0) ; - 每次取出堆顶节点
u ,用f_u 去更新f_v ; - 对于节点
v ,尝试将u 加入集合S ,若这一操作使得f_v 更小,则保留并将(v,f_v) 入堆。
当
| 复杂度 |
|---|
P7515 [省选联考 2021 A 卷] 矩阵游戏
给定一个
(n-1) \times (m-1) 的矩阵b_{i,j} ,你需要构造一个n \times m 的非负整数矩阵a_{i,j} ,满足0 \le a_{i,j} \le 10^6 ,且b_{i,j}=a_{i,j}+a_{i,j+1}+a_{i+1,j}+a_{i+1,j+1} 。输出构造或报告无解。多测,
T \le 10 ,n,m \le 300 ,1 秒,512 MB。
:::::success[题解]
根据黑白染色的套路,我们将方程两边同乘
记
于是将题目转化为构造矩阵
不妨钦定
我们考虑对第
- 若
i+j 为奇数,有-10^6 \le b_{i,j}+x_i-y_j \le 0 ; - 若
i+j 为偶数,有0 \le b_{i,j}+x_i-y_j \le 10^6 。
将不等式移项后可以整理出
| 使用 LLL+SLF 优化的 SPFA 可以通过。 |
|---|
AT_bogosortcontest_div1_g Source to Sink
给定一张
n 个点m 条边的有向图。一次操作选定零入度点u ,将u 为端点的边方向反转。最大化操作次数并输出,或报告操作无限进行。
多测,
\sum n \le 10^5 ,\sum m \le 2\times 10^5 ,2 秒,1024 MB。
:::::success[题解]
独立考虑原图的所有弱连通分量。如果存在 DAG 分量,翻转零入度点后不会产生有向环,操作次数无限。
设
考察有向边
断言 满足所有约束的非负整数解
证明 删去
初始边
由拓扑序保证
判环可以拓扑排序,构造
复杂度
:::::
QOJ7232 Odd Grammar
你初始有两种物品,记作
\tt{a} 和\tt{b} 。现存在n 种高级物品,给定m 条合成规则,第i 种合成规则形如使用[d_{i,1},d_{i,2},\cdots,d_{i,k_i}] 合成物品c_i ,满足c_i \in [1,n] ,d_{i,j} 可能是\tt{a},\tt{b} 或\in[1,n] 。判定是否存在某种合成方式,从奇数个初始物品开始,合成后仅剩余
1 个1 号物品。多测,
\sum n \le 5 \times 10^4 ,\sum m \le 2\times 10^5 ,输入字符数\le 5\text{MB} ,2 秒,512 MB。
:::::success[题解]
将第
将合并过程视作一棵
设
对虚点
- 若
\exists i, S_{d_i}=\varnothing ,原料不可用,规则暂时失效。 - 若
\forall i, \left|S_{d_i}\right|=1 ,所有原料只给出一种奇偶性,最终产生p_1 \oplus p_2\oplus \cdots p_k 。 - 若
\exists i, |S_{d_i}|=2 ,调整d_i 的取值可以两种奇偶。
使用 BFS 更新状态,当物品的
实现时,只要维护连向虚点的
:::::
CF1062F Upgrading Cities
给定一张
n 个点m 条边的有向无环图。定义u 是关键点,当且仅当存在至少n-2 个v 满足u \leadsto v 或v \leadsto u 存在。求关键点数目。
:::::success[题解]
对 DAG 进行拓扑排序,考察
- 若
|Q|=0 ,残余图所有点都从u 可达。 - 若
|Q| \ge 2 ,至少2 个不可达点,将u 标记为非关键点。 - 若
|Q|=1 ,设队内节点为x ,假想删去x 。对残余出边x \to y ,若y 成为新的零入度点,必有(u,y) 互不可达。否则删去x 后u 是唯一零入度点,残余图所有点可达。
综上所述,只需遍历x 的出边(x,y) 并检查y 是否是一度点:- 若存在一度点
y ,将u 标记为非关键点。 - 若不存在一度点
y ,更新u 的可达集大小。
- 若存在一度点
上述算法只处理了
总复杂度
:::::
P4581 [BJOI2014] 想法
给定一个
n 个点m 条边的有向无环图G 。对于每个非零入度点估算它能被几个零入度点到达。要求有95\% 的答案与标准答案的误差在25\% 以内。
:::::success[题解] 显然直接做不弱于 DAG 可达性,考虑随机化 + 近似算法。
结论:对于
因此考虑对零入度点赋一个随机权值
| 由于这个做法误差比较大,考虑随机多轮取平均值。做 |
|---|
P14362 [CSP-S 2025] 道路修复
给定
n 个点m 条边的无向连通图G=(V,E) ,边带权。现有
k 种决策,第i 种决策新建顶点x ,对所有u \in V 连边u \leftrightarrow x ,边权为a_{i,u} 。选择第i 种决策需要c_i 的代价。你可以选择任意决策,代价定义为新图 MST 边权和加上所选决策的总代价。最小化代价并输出。
:::::success[题解]
注意到
设
注意到 Kruskal 的瓶颈在排序,考虑将子图的边先排序,枚举时归并优化。复杂度
据说有
:::::
ZR3598 没啥题
给定
n 个区间[l_i,r_i] ,任意两个区间(i,j) 有边,边权为[l_i,r_i] \cap [l_j,r_j] 的长度。求最小生成树边权和。多测,
\sum n \le 2 \times 10^6 ,1 秒,512 MB。
:::::success[题解]
::::info[Boruvka 算法]
初始将
每轮操作中,同时考虑当前所有连通块,找出从块内出发连向其他块的最小边。将所有最小边同时加入
| 若边权互不相同,则合并过程不会成环,且每轮连通块数目折半,只会执行 |
|---|
考察 Boruvka 的初轮,我们需要对每个区间
假定交集非空,对
我们希望
- 最小化
r_i-l_j 取l_j 最大的区间x 。 - 最小化
r_j-l_i 取r_j 最小的区间y 。 - 最小化
r_j-l_j 取r_j-l_j 最小的区间z 。
这里我们丢掉
考虑一轮 Boruvka 后得到的最小边。除
我们注意到,这种形态的图只需要一轮 Boruvka 就能得到 MST!可以从三元环的情形类比过来。
于是直接找出每个区间的最小边相加即可,复杂度
:::::
AT_cf17_final_j Tree MST
给定一棵
n 个点的无根树,边带权,第i 个节点的点权为a_i 。构造
n 个点的完全图,边(u,v) 的权值为a_u+a_v+\text{dis}(u,v) ,其中\text{dis}(u,v) 为树链u \to v 的边权和。求最小生成树边权和。
:::::success[题解]
任意定根后,记
令
转而枚举
考虑做换根 DP:
- 对每个
x 维护a_v-2d_x 的最小值,其中v \in \text{subtree}(x) 。自底向上一次 DFS。 - 对每个
u 用(a_v-2d_x)_{\min} 更新最小边,其中u \in \text{subtree}(x) 。自顶向下一次 DFS。
还有一个约束需要考虑,上述过程最终求得的
解决方法是,我们同时记录最小值和次小值,并钦定最小值对应的
根据 Boruvka 进行
:::::
CF2081D MST in Modulo Graph
给定
n 个点的完全图,边(i,j) 的权值为\max(a_i,a_j) \bmod \min(a_i,a_j) 。求最小生成树边权和。多测,
\sum n, \sum \max a_i \le 5 \times 10^5 ,3 秒,500 MB。
:::::success[题解]
直接 Boruvka,问题变为给定
丢掉不同色的限制是套路的,维护最小值和次小值,并钦定二者颜色不同,信息构成交换半群。
设
-
若
a_i=x ,最小化a_j \bmod x 。枚举k=x,2x,3x,\cdots ,在区间[k,k+x) 中a_j \bmod x=a_j-k ,区间查询权值\min 即可。
进一步,权值\ge k+x 的点必然更劣,不会影响答案。预处理后缀信息并,直接做k 的后缀查询即可。 -
若
a_i=y ,最小化y \bmod a_j=y-\lfloor \frac{y}{x}\rfloor x 。
离线对x=a_j 枚举k=x,2x,3x,\cdots ,将j 挂在k 处,权值为-k 。
再对y 扫描线,每个j 最后被扫描的时刻恰为\lfloor \frac{y}{a_j}\rfloor \times a_j 。直接维护\min(-k) ,权值+y 即为所求。
注意实现细节,需要将值相等的
加上 boruvka 一只
:::::
:::::success[另解]
对
将点权相同的点缩起来处理,复杂度是调和型枚举,只会建
:::::
P9701 [GDCPC 2023] Classic Problem
构造
n 个点的完全图,其中m 条特殊边的边权给定,剩余边(i,j) 的权值为|i-j| 。求最小生成树边权和。多测,
n \le 10^9 ,m \le 10^5 ,\sum m \le 5 \times 10^5 ,8 秒,1024 MB。
:::::success[题解]
将特殊边的端点记为特殊点。在数轴上考虑问题,对于两个相邻的特殊点
我们将
考虑 Boruvka。对于点
- 从
u 出发的特殊边。 - 在
u 左侧最近的异块点v 连边(u,v) ,满足u\to v 无特殊边。 - 在
u 右侧最近的异块点v 连边(u,v) ,满足u \to v 无特殊边。
特殊边容易处理。后两种情形是对称的,这里只说明左侧点如何处理。
我们在 Boruvka 的每轮中,维护
考虑特殊边只有
:::::
P4768 [NOI2018] 归程
给定
n 个点m 条边的无向连通图,边有两种权值l_i,a_i 。多测,$T \le 3$,$n \le 2 \times 10^5$,$m,q \le 4 \times 10^5$,4 秒,512 MB。
:::::success[题解]
对于
考虑对
从
只需求出最浅的
| 视 |
|---|
P6765 [APIO2020] 交换城市
给定
n 个点m 条边的无向带权连通图。$n \le 10^5$,$m,q \le 2 \times 10^5$,1.5 秒,512 MB。
:::::success[题解]
先考虑怎么判定有解。经过思考,我们发现
情况一:环
如图所示,此时
情况二:三度点
如图所示,此时
概括一下,只要
考虑带权并查集,记录
定义
在原本的重构树上,
考虑环的问题如何解决,可以魔改一下 Kruskal 重构树的形态。在 Kruskal 过程中,若
| 在查询时,LCA 上方额外多出一个新点,因此环的情形也能被 |
|---|
P2619 [国家集训队] Tree I
给定
n 个点m 条边的无向带权连通图,每条边有黑白两色。求恰好有k 条白色边的生成树中,边权和最小的生成树,并输出答案。
:::::success[题解]
我们声称答案关于
考虑 WQS 二分斜率
注意到二分时只要合并黑边和白边两个有序数组,可以归并优化,做到
类似题目是 P5633。两个题的注意事项可以参见讨论区。
:::::
CF1054G New Road Network
现有
n 个点和m 个集合S_i ,构造一棵n 个点的树T ,使得\forall i \in [1,m], S_i 的导出子图连通。输出构造或报告无解。多测,
\sum n, \sum m \le 2 \times 10^3 ,2 秒,250 MB。
:::::success[题解]
对集合
设所有
另一方面,记
取完全图
:::::
CF1325F Ehab's Last Theorem
给出一个
n 个点m 条边的连通无向图,找到一个大小为\lceil\sqrt{n}\rceil 的独立集,或者一个大小不小于\lceil\sqrt{n}\rceil 的环,输出构造。
:::::success[题解]
考虑拉出一棵 DFS 生成树,如果存在一条返祖边,其端点深度差
反之考虑按深度模
| 复杂度 |
|---|
P6954 [NEERC 2017] Connections
给定一张
n 个点m 条边的强连通有向图,保证n \ge 4 \land m>2n 。你需要保留恰好2n 条边,使图仍然强连通,输出构造。多测,
\sum m \le 10^5 ,3 秒,512 MB。
:::::success[题解]
任取一点
注意到
复杂度
:::::
CF1519E Off by One
给定
n 个点(x_i,y_i) ,每个点可以变成(x_i+1,y_i) 或(x_i,y_i+1) 。若(0,0),(x_i,y_i),(x_j,y_j) 三点共线则可以匹配i,j 并删去。求最大匹配,并输出一组方案。
:::::success[题解]
直观的想法是若
进行点边转化,将斜率视作顶点,点视作边。记
问题是
对
拉出一棵 DFS 树,自底向上贪心。设计函数 dfs(u) 返回
- 若
v 未访问,调用dfs(v)得到e' 。- 若
e' 存在,则将e 和e' 配对。 - 若
e' 不存在,则保留e 。
- 若
- 若
v 已访问,说明u\to v 是返祖边,也保留e 。
遍历结束后,将被保留的
总复杂度
:::::
P4151 [WC2011] 最大 XOR 和路径
给定
n 个点m 条边的无向图,边带权。将1\leadsto n 路径的权值定义为边权异或和,求最大权值。允许多次经过某点或某边。
:::::success[题解]
对于图上的某个环,我们可以在环上绕一圈并原路返回,权值只剩下环的异或和。故任意环的异或和都是可选择的。
下面说明,路径必能表示为任意
以
移项得
合法权值的集合就是
:::::
CF1091E New Year and the Acquaintance Estimation
给出一个长为
n 的序列d_1 \sim d_{n} 。求所有可能的d_{n+1} ,使得d_1 \sim d_{n+1} 可简单图化。:::::info[可简单图化]
可简单图化的意思是,存在一个
n 个点的简单无向图,使得节点i 的度数为d_i 。:::::
::::::success[题解]
:::::info[Havel-Hakimi 定理]
考虑降序排序的度数序列
:::::
:::::info[Erdős-Gallai 定理]
考虑降序排序的度数序列
:::::
枚举
实际上,定理的成立性关于
如果固定调整方向,就可以用二分求出答案的上下界。
根据定理成立的第一个条件,我们可以得到
复杂度
::::::
AGC016D XOR Replace
给定长为
n 的序列a_i,b_i 。一次操作选择一个i ,令a_i\gets\bigoplus\limits_{k=1}^n a_k 。求将a 变为b 的最小操作次数,或报告无解。
:::::success[题解]
令
对于位置
这启示我们建图
同理令
对于数值
我们顺次扫描
- 若
a_{n+1} 包含在|C| 中,我们需要走|E| 步并在|C|-1 个连通块之间跳跃。每次跳跃需要一次额外交换,操作次数|E|+|C|-1 。 - 若
a_{n+1} 不包含在|C| 中,我们需要先做一次额外交换,操作次数|E|+|C| 。
复杂度
:::::
P9731 [CEOI 2023] Balance
给定一个
m\times k 的矩阵,值域为[1,n] 。你需要将每行重排,使得\forall i\in[1,n] ,数字i 在所有列中出现次数的极差不超过1 。输出构造。保证\mathbf{k} 是\mathbf{2} 的幂。
:::::success[题解]
考虑
建图
将其推广到一般情形。对列分治,设当前区间为
具体地,考虑连边
复杂度
:::::
P10873 [COTS 2022] 帽子 Šeširi
现有
n 个人头上戴着红色或白色的帽子,每个人只能看到别人的帽子颜色,他们会根据别人的帽子颜色猜测自己头上帽子的颜色。你需要为每个人构造一组猜测策略,使得对于所有
2^n 种情况都满足以下条件:
- 设有
b 人戴了白色帽子,其中至少有\lfloor\frac{b}{2}\rfloor 人猜对自己帽子的颜色。- 设有
c 人戴了红色帽子,其中至少有\lfloor\frac{c}{2}\rfloor 人猜对自己帽子的颜色。输出构造。
:::::success[题解]
对于所有
更直观的说,对第
考虑图论建模,连无向边
一个状态下猜对的人就是这个节点的入度。弱化题目的限制,即要求猜对的人数至少为
回到原题,我们将一个状态拆成两个点
| 复杂度 |
|---|
AGC025E Walking on a Tree
给出一棵
n 个点的无根树,再给定m 个二元组(u_i,v_i) 。你需要依次考虑i=1,2,\cdots,m ,选择从u_i 游走到v_i ,或从v_i 游走到u_i 。第
i 次的游走的得分定义为,游走路径上满足如下条件之一的边的数目:
- 在前
i-1 次游走中,该边未被经过。- 在前
i-1 次游走中,该边的所有遍历方向恰与本次相反。最大化总得分,并构造一组方案。
::::::success[题解]
先尝试分析理论上界。容易用树上差分得到第
- 若
c_i=0 ,它不会提供任何得分。 - 若
c_i=1 ,它只被遍历一次,必然产生1 的得分。 - 若
c_i\ge2 ,它最多被正反遍历两次,至多产生2 的得分。
因此,得分的理论上界是
断言上界可以取到。为了给出构造式证明,必须让
考虑对
假定所有连通块都是欧拉图,则可以对每个连通块跑出一条欧拉回路,由出入度平衡的性质构造必然合法。
:::::error[错解]{open}
考虑建超级源点对所有奇度数点连边,再跑欧拉回路。
::::info[Hack]
考虑树的结构
建立的虚图边为
定向方案为
::::
:::::
使用另一种处理奇度数点的手法。注意到对于树上节点
这样调整之后,我们再对每个连通块跑欧拉回路,得到定向方案即可。
复杂度
::::::
CF555E Case of Computer Network
给出一个
n 个点m 条边的无向图。给定k 对节点(u_i,v_i) ,你需要将所有边定向,使得任意u_i \leadsto v_i 可达。判定是否存在可行方案。
:::::success[题解]
Robbins 定理 连通分量可定向为 SCC,当且仅当连通分量是 E-DCC。
对原图缩 E-DCC 得到一棵树。判掉
使用树上差分标记方向,若某条边同时确定为
复杂度
:::::
QOJ15449 Finances
现有
n 个人,第i 个人持有a_i 元,负数表示债务,保证\sum\limits_{i=1}^n a_i=0 。记A=\sum \limits_{i=1}^n \max(0,a_i) 。给定
m 条交易关系(u,v,c) ,表示u \leftrightarrow v 之间可以相互转账,总额度不超过c 。保证关系网连通,任意边c \ge \lceil A/2 \rceil 。求若干次转账后能否使得每人持有
0 元。多测,
\sum n ,\sum m \le 10^6 ,3 秒,1024 MB。
:::::success[题解]
注意到
边双缩点,新点权值
对
对树一次 DFS 即可判定。总复杂度
:::::
P3225 [HNOI2012] 矿场搭建
给定一个
n 个点m 条边的连通无向图。你需要设置若干关键点,使得任意一个点删掉后,其余点总能到达一个关键点。输出关键点的最少数目,以及达成此数目的方案数。保证答案
< 2^{64} 。
:::::success[题解]
考虑求出所有割点。此时对于一个大小为
- 若割点数目
>1 ,删去任意点总能连通,故无需设置特殊点。 - 若割点数目
=1 ,则在除割点外的点设置特殊点即可;如果这个特殊点被删,通过割点可以到达其他特殊点。方案数为k-1 。 - 若无割点,则任选两个点作为特殊点,删去点后总能连通,方案数为
\binom{k}{2} 。
| 复杂度 |
|---|
QOJ14810 Trajan Algorithm
有错误的求割点「Trajan 算法」,问题在于返祖边转移
\text{low}_u \gets \text{low}_v 。给定一张n 个点m 条边无向图,出边顺序确定,求会被错判的所有点。多测,
\sum n, \sum m \le 10^6 ,2 秒,1024 MB。
:::::success[题解]
割点判定定理是
考察下图所示的情形:
标准 Tarjan 算法令
而 DFS 回溯时
在
结论 割点
等价表述是,
复杂度
:::::
P9697 [GDCPC 2023] Canvas
现有长为
n 的序列a_i ,初始a_i=0 。给定m 次操作(u_i,v_i,x_i,y_i) ,保证x_i,y_i \in \{1,2\} 。操作令a_{u_i} \gets x_i, a_{v_i} \gets y_i 。你可以按任意顺序执行操作,最大化
\sum \limits_{i=1}^n a_i 并输出构造。多测,
\sum n,\sum m \le 5 \times 10^5 ,3 秒,1024 MB。
:::::success[题解]
时光倒流,将覆盖操作转化为,首次操作后数值固定不变。
不难发现
不妨设
- 若原图强连通,任意选点后 DFS,则只有 DFS 树根节点为
1 ,其余点全为2 。 - 若图是 DAG,按照拓扑序操作,只有零入度点为
1 ,其余点全为2 。
对有向图进行 SCC 缩点,按缩点后拓扑序操作即可。注意零入度 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] 有效。
每条边
注意精细实现,只遍历
总复杂度
:::::
CF1989F Simultaneous Coloring
现有一个
n \times m 的网格,你可以将一列涂黑,或者将一行涂白。每轮可以同时进行
k 次操作,代价为[k>1]k^2 。对于同时受到两类操作影响的格子,颜色可以自由选定。进行
q 次操作,给定(x,y,c) ,增加一条限制,格子(x,y) 必须涂成颜色c 。每次操作后,输出满足所有要求的最小代价。
:::::success[题解]
显然行列至多操作一次。设第
考虑用
分析可得,最优策略一定是对每个 SCC 整体操作,再按缩点后拓扑序依次操作。答案即为所有 SCC 点数平方和。
离线时间轴分治求出每条边的闭合时刻
视
:::::
P9139 [THUPC 2023 初赛] 喵了个喵 II
给定一个长为
4n 的序列,其中1\sim n 各出现4 次。你需要将其划分为两个相等的子序列,输出构造或报告无解。
:::::success[题解]
考虑问题的弱化,即
结论 无解当且仅当
1221 和 1212 是很好的例子。如果有解,则只要将
受上述讨论启发,记数值
实际上,我们只要关注前两种划分方案。设布尔变量
-
这个约束的实际意义是,对于两个导致包含关系的选择,禁止二者同选。其他情形同理。
这是一个 2-SAT 问题。对约束中的
转二维平面分析,则
可以做主席树优化建图,或者 CDQ 分治套前缀优化建图,Tarjan 求解复杂度
不过我们还有一种更聪明的手法,可以使用 Kosaraju 求 SCC,这样只要两次 DFS。考虑这篇文章中提及的技巧,假设节点
使用线段树维护左端点
注意两次 DFS 时正反图的对应关系。复杂度仍为
:::::
CF487E Tourists
给定一张
n 个点m 条边的无向连通图,点带权w_i 。进行q 次操作:
- 给定
i,x ,令w_i \gets x 。- 给定
u,v ,查询u \leadsto v 所有简单路径中,点权\min 的最小值。
:::::success[题解]
两个
建立广义圆方树,转化为单点修改,链
我们将圆点权值挂在邻域方点上,在方点处用 multiset 记最小值,只要使用普通树剖套线段树解决。复杂度
:::::
P4630 [APIO2018] 铁人两项
给定一张
n 个点m 条边的无向图。对三元组(s,x,t) 计数,满足存在s \leadsto t 的简单路径过点x 。
:::::success[题解]
建立原图的广义圆方树,则
我们将圆点的权值赋为
将贡献拆到每个点上,容易求出有多少对
复杂度
:::::
P16136 [ICPC 2018 NAIPC] Winter Festival
给定一张
n 个点m 条边的无向图。你需要将边赋一组权w(e) ,满足下列条件:
- 边权
w(e) \in \{0,1,2\} 。- 对任意简单环
C ,\sum \limits_{e \in C} w(e) \equiv 1 \pmod 2 。- 对任意点
u 的任意出边e_1,e_2 ,(w(e_1)+w(e_2)) \bmod3 \ne 1 。最小化
\sum \limits_{e \in E} w(e) 并输出,或报告无解。
:::::success[题解]
性质 有解的必要条件是
证明 设简单环
三式相加得
左式显然为偶数,矛盾。故原图必为边仙人掌。
建立原图的广义圆方树,并在圆方树上 DP。设
- 仅考虑圆点
u 子树内部。 - 所有原图边已赋权,满足约束。
- 对方点
v \in \text{son}(u) ,所有(u,v) 边颜色构成集合S 。
根据约束,合法的S 满足0,1 不共存,2 至多出现一次,从而至多6 种。下文使用集合符号表述,但注意合并集合时拒绝2 的重复。
设方点
为方便书写,定义两个辅助量,对圆点
意义是方点父亲接 1/2 条边的代价。对边仙人掌,方点必定为桥或简单环,下面讨论方点 DP。
若方点
若方点
-
设
g_{i,y,s} 表示满足下列条件的最小代价:- 仅考虑环上前
i 条边e_1 \sim e_i 。 -
-
- 仅考虑环上前
-
枚举
w(e_{i-1})=y \land w(e_i)=z ,容易列出转移g_{i,z,s+z} \gets g_{i-1,y,s} + A_{v_i}(y,z)+z -
DP 初值为
g_{0,a,a}=a 。 -
枚举
w(e_0)=a \land w(e_k)=b ,则传递h_{p,\{a,b\}} \gets g_{k,b,1} 。
初始 DP 令
总复杂度
:::::
QOJ5407 基础图论练习题
给定一张
n 个节点的竞赛图。对所有点对(u,v) 求出,翻转边(u,v) 后 SCC 的数目。
:::::success[题解]
根据 Landau 定理只要求得
::::info[Landau 定理] 引理 竞赛图缩 SCC 后形成链状图,每个拓扑序在前的 SCC 向在后的所有 SCC 连边。
设竞赛图节点
Landau 定理
| 证明 参见 https://www.cnblogs.com/acha/p/9042984.html,此处不再赘述。 |
|---|
设
设修改令
- 若
a \le b ,只有k \in [L_a,R_b) 的f_k \gets f_k-1 ,变化量为[*=1]-[*=0] 。 - 若
a \ge b+2 ,只有k \in [R_b,L_a) 的f_k \gets f_k+1 ,变化量为-[*=0] 。 - 若
a=b+1 则无变化。
对
:::::
P3561 [POI 2017] Turysta
给定一张
n 个节点的竞赛图。对于每个点u 求出从u 出发的最长简单路径,输出构造。
::::::success[题解]
利用 Landau 定理推论找出所有 SCC 并缩点后,DAG 的形态是链状图。
考虑找出每个 SCC 的哈密顿回路。根据 DAG 的形态,直接取一段后缀的哈密顿回路拼起来,就能构成一条简单路径。
这样,这个问题的做法就显然了:利用 Camion-Moon 定理的构造求得 SCC 的哈密顿回路。对于一点
::::info[Redéi 定理 & Camion-Moon 定理] 竞赛图哈密顿路 & 哈密顿回路构造问题。
Redéi 定理 任何一个竞赛图都至少存在一条哈密顿路。
构造 考虑增量构造。假设我们已经排好了
直接模拟的复杂度为
Camion-Moon 定理 一个竞赛图存在哈密顿回路,当且仅当它是强连通的。
构造 先用 Redéi 定理的构造找出一条哈密顿路,然后在路径上顺序扫描。
想象我们当前位于点
我们尝试将
-
若存在
(c_i, x) \in E, (x, c_{i+1}) \in E ,可以直接将x 插入c_i.c_{i+1} 之间。 -
否则,我们维护集合
A=\{u \mid (c_i,u) \notin E\} ,B=\{u \mid (u,c_i) \notin E\} ,即不被任何环内节点指向的A 和不指向任何环内节点的B 。不妨设x \in A 。
由于图是强连通的,必然存在y \in B, (y,x) \in E 。只要将x,y 一起插入环中。
我们在环中随意找一条边,比如c_1 \to c_2 。根据A,B 的定义,有(c_1,y),(x,c_2) \in E 。将c_1 \to y \to x \to c_2 插入即可。
| 精细实现复杂度 |
|---|
精细实现复杂度
::::::
P6790 [SNOI2020] 生成树
给出一张
n 个点m 条边的无向连通图,保证G 在删去某条边后是仙人掌。求G 的生成树数目,对998244353 取模。
:::::success[题解]
我们声称
设计 DP 状态为
- Rake:孤立边必选,将
f_e 乘进答案。 - Compress:边
e_1,e_2 至少有一条在生成树上,对于等效边e 满足 -
- Twist:边
e_1,e_2 不能同时在生成树上, 对于等效边e 满足 -
复杂度 1log。代码。
::::info[广义串并联图方法]
广义串并联图,GSPG,定义是不存在同胚于
- 广义串并联图的树宽和分支宽至多为
2 。 - 因为广义串并联图不存在同胚于
K_4 的子图,自然也不可能包好同胚于K_5 或K_{3,3} 的子图。由 Kuratowski 定理,GSPG 必为平面图。 - 广义串并联图必能
3 染色。
在 OI 中,我们最常用的是广义串并联图方法。
- Compress / 缩二度点 / 消串联:删去一个二度点,将两端的点建新边。
- Twist / 叠重边 / 消并联:将两条重边叠合成一条。
- Rake / 删一度点 / 去断路:删去一个一度点与其出边。
如果图是广义串并联图,则可以通过如上三种操作缩为单点。对于一般图,若
实现时,我们用 std::map 维护邻接矩阵,用队列维护度数
| 使用广义串并联图方法的题,难点主要在于设计 DP 状态,并讨论三种操作时 DP 值转移的等效性。 |
|---|
:::::
QOJ9278 Linear Algebra Intensifies
维护一个
n \times n 的矩阵A 。m 次操作给出l,r ,对所有i \in [l,r], j \in [l,r] ,令A_{i,j} \gets A_{i,j}+1 。操作结束后求\det A \bmod 998244353 。
:::::success[题解]
结论 行列式在二维差分后不变。
对矩阵
观察 Matrix-Tree 定理的形式,发现度数矩阵减邻接矩阵的系数正好对上,将问题转化为连边
建图以后,使用和上一题相同的广义串并联图方法,将问题规约到
考虑使用 Matrix-Tree 定理求子图生成树数目。我们要求的是
在
:::::