「做题记录」图论选做

· · 算法·理论

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[题解]

拆点,状态 (u,x) 表示当前位于节点 u,持有数字 x。记 d_u 为 u 的出度,则 x>d_u 无意义,状态数 O(m)。

对 w 预处理前缀和后,按照题目要求建图,从 (1,1) 开始跑 Dijkstra 即可。复杂度 O(m \log m)。

:::::

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[题解]

拆点,状态 (u,i) 表示当前位于节点 u,折半操作进行 i 次,容易建图列出转移,从 (1,0) 开始跑 dij 即可。

状态数为 O(nk),无法通过。注意到折半操作进行多次后代价很小,而精度要求较为宽松,将 k 与上界 -\log_2 \epsilon 取 \min,状态数 O(n \log \frac{1}{\epsilon}) 可以通过。代码。

:::::

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[题解]

显然可以拆点 (u,h) 做到 O(nV) 状态数。

考虑堆优化 Dijkstra 的过程。我们声称,最先入堆的 (u,h) 状态支配后续所有 (u,h') 状态。

设 d_1=\text{dis}(u,h),d_2=\text{dis}(u,h'),显然 d_1 +|h_1-h_2| \le d_2。从而 (u,h) \to (u,h') 后执行后续决策不劣,只记录 (u,h) 是正确的。

堆内记录 (u,h,\text{dis}) 三元组,转移时只检查 1\leadsto u 的代价,最终取出 (n,h) 加上 a_n-h 输出即可。不难发现上述过程类似堆优 dij,复杂度 O(m \log m)。代码。

:::::

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[题解]

对询问二分答案 x,将 >x 的边权视作 1,\le x 的边权视作 0。则 x 成为 u \leadsto v 上第 k 大,当且仅当 u \leadsto v 的最短路 <k。

按边权从小到大加边,加到 w_i 表示 \le w_i 的边权都视作 0。维护每个时刻的全源最短路,Floyd 可以 O(n^2) 更新,总复杂度 O(n^2m)=O(n^4)。

考虑优化,我们添加一个剪枝:将 0 边连接的点缩起来,若端点同块就跳过。有效的合并数目只有 n-1 次,现在复杂度就是 O(n^3+q \log n) 的了。代码。

:::::

P11795 [JOI 2016 Final] 铁路票价 / Train Fare

给定一张 n 个点 m 条边的无向连通图,初始所有边权均为 1。进行 q 次操作,将某条边的权值改为 2。操作结束后,求 1\leadsto u 最短路大于原图的 u 点数目。

:::::success[题解]

对于最短路长度不变的点,新的最短路必不经过边权为 2 的边,故操作等价于删边。

建立最短路图,若边 u \to v 不在图上则忽略。否则从 v 开始拓扑排序,将 v 的后继边全部删去,并将零入度点统计答案。注意到每条边只会删一次,复杂度均摊 O(m)。

原图边权为 1,可以用 BFS 建立最短路图,总复杂度 O(n+m)。代码。

:::::

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

给定一张 n 个点 m 条边的有向带权图。你可以翻转至多一条边 i 的方向,并产生 d_i 的代价。

操作结束后,你需要从 1 走到 n,再从 n 回到 1,代价为路径边权和。最小化总代价并输出,或报告无解。

:::::success[题解]

建立以 1 为根的最短路树 T_1 和以 n 为根的 T_2。我们枚举翻转的边 e=(u,v) 进行讨论:

对于 T_2 同理分讨,将两部分相加即可。

总复杂度 O(n^3+m\log m)。代码。

:::::

ZR3778 地铁

给定一棵 n 个点的有根树,根节点为 1,树边权值为 a。再给出 m 个点对 (u_i,v_i),对 u_i \leadsto v_i 树链上每个点 x 连单向边 u_i \overset{2b}\to x。

求 1 号点到每个点的最短路长度。

:::::success[题解]

性质 1 设 d_i 为 1 \leadsto i 的最短路,必有 d_{\text{fa}(u)} \le d_u, \forall u。

性质 2 令 x_i=\text{lca}(u_i,v_i),只需保留 x_i \leadsto v_i 树链连边。

根据上述两个性质,可以得到优化建图方法:

在新图上跑单源最短路即可。边权只有三种,使用三个队列模拟小根堆,复杂度 O(n+m)。代码。

:::::

P4745 [CERC2017] Gambling Guide

给定一张 n 个点 m 条边的无向图。你需要从起点 1 走到终点 n。当你位于节点 u 时,你可以支付 1 的代价并获得一次前往邻接点 v 的机会,你可以选择放弃机会。

你需要使最终到达终点的概率为 1,并最小化期望代价。输出期望值,精度要求 10^{-6}。

:::::success[题解] 记 f_u 为从节点 u 出发到达终点的最小期望代价,d_u 为节点 u 的步数,N(u) 为节点 u 邻接点构成的集合。显然 f_n=0。

当我们位于节点 u 且获得了去往 v 的机会时,需要决策是否接受这个机会。为此,钦定一个非空集合 S \subseteq N(u),当 v \in S 时我们接受,否则不接受。

此时 P(v \in S)=\frac{|S|}{d_u}。由几何分布,节点 u 处的期望代价为 \frac{d_u}{|S|}。且获得 S 中任意节点的概率是相同的,因此有

f_u=\frac{d_u}{|S|}+\frac{1}{|S|}\sum_{v \in S} f_v=\frac{d_u+\sum_{v \in S} f_v}{|S|}

从上面的式子可以看出,为了让 f_u 最小,我们应当按 f_v 升序将 v 加入 S 中。只要 v 的加入可以使得 f_u 最小就保留。

这一过程非常类似 Dijkstra。最优化 DP 在有环图上的转移顺序正是最短路,因此给出如下流程:

当 u 出队时,所有小于 f_u 的 f_v 已经用来松弛过 f_u,故 f_u 一定取到了最优。这样就不会存在重复入队答案更优的可能性,故上述算法是正确的。

复杂度 O(m \log n)。代码。

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[题解] 根据黑白染色的套路,我们将方程两边同乘 (-1)^{i+j} 有

(-1)^{i+j}b_{i,j}=(-1)^{i+j}a_{i,j}-(-1)^{i+j+1}a_{i,j+1}-(-1)^{i+j+1}a_{i+1,j}+(-1)^{i+j+2}a_{i+1,j+1}

记 c_{i,j}=(-1)^{i+j} a_{i,j},那么

(-1)^{i+j}b_{i,j}=c_{i,j}+c_{i+1,j+1}-c_{i+1,j}-c_{i,j+1}

于是将题目转化为构造矩阵 c_{i,j}。

不妨钦定 c_{i,1}=c_{1,j}=0,根据方程先递推出一组 c_{i,j},然后调整。

我们考虑对第 i 行加一个数 x_i,第 j 行减一个数 y_j,上面的方程仍然成立。分类讨论 x_i,y_j 的约束:

将不等式移项后可以整理出 x_i-y_j 的范围。我们将 x,y 视为同一种未知数,可以用差分约束跑出一组 x_i,y_j,并且可以判掉无解。

使用 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 分量,翻转零入度点后不会产生有向环,操作次数无限。

设 x_u 为节点 u 的操作次数,若 u 在有向环上必有 x_u=0。

考察有向边 u \to v,将操作序列中 \ne u,v 的部分都删掉,那么必然是 u,v,u,v,\cdots 交替,从而

x_v \le x_u \le x_v+1

断言 满足所有约束的非负整数解 x_1\sim x_n,均能通过合法操作取到。

证明 删去 x_u=0 的 u,残余部分必为 DAG,取出任意拓扑序。第 k 轮操作按同一个拓扑序操作所有 x_u \ge k 的 u。

初始边 u \to v 的约束只有两种:

由拓扑序保证 u 先于 v 操作,所有操作合法,而节点 u 恰好操作 x_u 次。

判环可以拓扑排序,构造 x_1 \sim x_n 可以对差分约束系统 01BFS。

复杂度 O(n+m)。代码。

:::::

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[题解]

将第 i 种合成规则作为虚点 i',连边 d_{i,j} \to i' 和 i' \to c_i。虚点 i' 激活当且仅当所有前驱 d_{i,j} 激活,实点 c_i 激活只要存在前驱 i' 激活。

将合并过程视作一棵 1 为根的根向生成树,题目要求叶子 \tt{a},\tt{b} 的数目为奇数。

设 S_u 为合成 u 可实现的叶子数奇偶性,记录 S_x \subseteq \{0,1\} 只有 4 种。初始 S_{\tt{a}}=S_{\tt{b}}=\{1\},判定 1 \in S_1。实点是逻辑 OR,对应集合并,虚点是逻辑 AND。

对虚点 [d_1,d_2,\cdots,d_k] \to c 简单讨论:

使用 BFS 更新状态,当物品的 S_u 改变时扔进队列,并更新所有关联点。更新至多 2 次,故总复杂度线性。

实现时,只要维护连向虚点的 \varnothing 数目,是否有 \{0,1\} 连入,以及入点异或和等。视 n,m,\sum k_i 同阶复杂度 O(n)。代码。

:::::

CF1062F Upgrading Cities

给定一张 n 个点 m 条边的有向无环图。定义 u 是关键点,当且仅当存在至少 n-2 个 v 满足 u \leadsto v 或 v \leadsto u 存在。求关键点数目。

:::::success[题解]

对 DAG 进行拓扑排序,考察 u 出队的时刻。对任意 v \in Q,必有 u,v 互不可达。

上述算法只处理了 u 的后继,在反图上同理求出前驱数即可。

总复杂度 O(n+m)。代码。

:::::

P4581 [BJOI2014] 想法

给定一个 n 个点 m 条边的有向无环图 G。对于每个非零入度点估算它能被几个零入度点到达。要求有 95\% 的答案与标准答案的误差在 25\% 以内。

:::::success[题解] 显然直接做不弱于 DAG 可达性,考虑随机化 + 近似算法。

结论:对于 n 个均匀随机的实数 x_1 \sim x_n,有 \mathbb{E}[\min x_i]=\frac{1}{n+1}。

因此考虑对零入度点赋一个随机权值 a_i,然后拓扑序上 DP 求出每个点可达的 \min a_i,用 \frac{1}{a_i}-1 作为估计答案。

由于这个做法误差比较大,考虑随机多轮取平均值。做 k 轮的复杂度为 O(mk),取 k=200 可以稳定通过。

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[题解]

注意到 k\le 10,考虑枚举每个决策是否选择,对新图使用 Kruskal 求 MST,复杂度 O(2^k m\log m)。

设 G 的 MST 为 T,上述过程中,来自原图的边可以只保留 T 中的边,从而 O(m) 的边数降到 O(nk),总复杂度 O(m \log m+2^knk\log n)。

注意到 Kruskal 的瓶颈在排序,考虑将子图的边先排序,枚举时归并优化。复杂度 O(m \log m+2^knk\alpha(n)),精细实现可以通过。代码。

据说有 O(nk2^k) \sim O(n2^k) 做法,这也太牛了。

:::::

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 算法] 初始将 n 个顶点视作 n 个连通块。

每轮操作中,同时考虑当前所有连通块,找出从块内出发连向其他块的最小边。将所有最小边同时加入 T 并合并连通块。

若边权互不相同,则合并过程不会成环,且每轮连通块数目折半,只会执行 O(\log n) 轮。如果有相同边权,可以人为钦定第二关键字得到一个严格全序。

考察 Boruvka 的初轮,我们需要对每个区间 i 找到最小边对应的另一端点 j。边 (i,j) 的边权为

w(i,j)=\max(0,\min(r_i,r_j)-\max(l_i,l_j))

假定交集非空,对 \min 和 \max 分类讨论:

我们希望 w(i,j) 取极值,从而最优的 [l_j,r_j] 一定为以下三者之一:

这里我们丢掉 i \ne j 的限制,从而包含 w(i,j)=r_i-l_i 的情形。

考虑一轮 Boruvka 后得到的最小边。除 x 外的所有顶点,选出的最小边必然指向 x,y,z 之一。取出所有可能的最小边,画出边的导出子图:

我们注意到,这种形态的图只需要一轮 Boruvka 就能得到 MST!可以从三元环的情形类比过来。

于是直接找出每个区间的最小边相加即可,复杂度 O(n)。

:::::

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[题解]

任意定根后,记 d_u 为 u 根链的边权和,将 \text{dis}(u,v) 拆开:

w(u,v)=a_u+a_v+d_u+d_v-2d_{\text{lca}(u,v)}

令 a_u \gets a_u+d_u。考虑 Boruvka 的过程,我们需要为每个点 u 找到最小边 u \to v 使得 a_v-2d_{\text{lca}(u,v)} 最小。

转而枚举 x=\text{lca}(u,v),并在 x 子树内更新 u 的答案。这里我们不需要钦定 u,v 属于异侧子树,因为 d_x<d_{\text{lca}(u,v)} 导致在 x 处更新 (u,v) 不优,故不会被计入答案。

考虑做换根 DP:

还有一个约束需要考虑,上述过程最终求得的 u,v 有可能同属一个连通块,而我们要求 u,v 属于不同块。

解决方法是,我们同时记录最小值和次小值,并钦定最小值对应的 v 和次小值对应的 v 不在同块内。在 u 处更新答案时,如果 u 和最小值对应的 v 同块,就转而用次小值更新。

根据 Boruvka 进行 O(\log n) 轮,每轮复杂度线性,总复杂度 O(n \log n)。代码。

:::::

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,问题变为给定 i 的颜色 c_i,对每个 i 找到 c_i \ne c_j 且 \max(a_i,a_j) \bmod \min(a_i,a_j) 最小的 j。

丢掉不同色的限制是套路的,维护最小值和次小值,并钦定二者颜色不同,信息构成交换半群。

设 x=\min(a_i,a_j),y=\max(a_i,a_j)。对 a_i 分讨:

注意实现细节,需要将值相等的 a_i 缩起来处理,复杂度才是调和型枚举的 O(V \log V)。

加上 boruvka 一只 \log 得到 O(n \log n\log V) 的复杂度,可以通过。代码。

:::::

:::::success[另解]

对 x=\min(a_i,a_j) 考察区间 [kx,(k+1)x)。若区间中两数 y_1<y_2,必有 y_2 \bmod x >y_1 \bmod x。换言之,每个 [kx,(k+1)x) 只有最小值有用。

将点权相同的点缩起来处理,复杂度是调和型枚举,只会建 O(V \log V) 条边。视 n,V 同阶,Kruskal 即可做到 O(n \log^2 n),精细实现可以 1log。

:::::

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[题解]

将特殊边的端点记为特殊点。在数轴上考虑问题,对于两个相邻的特殊点 x,y,容易发现 (x,y) 内的点一定连成一条链。

我们将 (x,y) 缩成一个点,并将答案加上链的权值和。这样图就只有 2m 个顶点了。

考虑 Boruvka。对于点 u,从 u 向外的最小边必然为以下三者之一:

特殊边容易处理。后两种情形是对称的,这里只说明左侧点如何处理。

我们在 Boruvka 的每轮中,维护 f_u 表示 u 左侧最近的异块点 v。查询时从 v \gets f_v 开始,若 u \to v 有特殊边则令 v \gets v-1,若 u,v 同块则令 v \gets f_v,直到 v 合法。

考虑特殊边只有 m 条边,故 v \gets v-1 操作总共 m 次,均摊下来每轮复杂度线性。总复杂度 O(m \log m)。代码。

:::::

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[题解] 对于 u,v,u \to v 在 a_i 上可达的充要条件为两点之间最大瓶颈路的权值 >k。

考虑对 a_i 求最大生成树,建立 Kruskal 重构树。这样 u \to v 可达当且仅当其 LCA 点权 >k。

从 1 开始关于 l_i 跑 Dijkstra,求出每个点到 1 的最短路。

只需求出最浅的 u 的祖先,满足其祖先的点权 >k,则祖先对应子树中叶子的最短路 \min 即为答案。第一步树上倍增,第二步 DFS 预处理。

视 n,q,m 同阶复杂度 O(n \log n)。

P6765 [APIO2020] 交换城市

给定 n 个点 m 条边的无向带权连通图。

$n \le 10^5$,$m,q \le 2 \times 10^5$,1.5 秒,512 MB。

:::::success[题解] 先考虑怎么判定有解。经过思考,我们发现 u,v 可以交换的情况有如下两种:

情况一:环

如图所示,此时 1,2 互换位置可以令 1 \to 3, 2 \to 1, 3 \to 2。

情况二:三度点

如图所示,此时 1,2 互换位置借助一个 \ge 3 度的点 3,令 1 \to 3 \to 4, 2 \to 3 \to 1, 1 \to 3。

概括一下,只要 u,v 所在连通块非链即可。于是我们会了怎么判定无解。

考虑带权并查集,记录 c_{1/2,x} 表示 x 集合内 1/2 度点的数目,s_x 表示 x 集合的大小,则 x 集合为链当且仅当 c_{1,x}=2 \land c_{1,x}+c_{2,x}=s_x。

定义 h_x 为:x 在 Kruskal 重构树上的祖先中,深度最深的非链连通块代表元。我们首先要解决如果判定连通块是否为链,这样一次 DFS 即可处理得到 h_x。

在原本的重构树上,u,v 之间的瓶颈路为 LCA 的点权。而现在引入 h_x 的目的即为修正 LCA 的答案,即 h_{\text{lca}} 作为最终答案。这样我们就解决了 \ge 3 度点对答案的影响。

考虑环的问题如何解决,可以魔改一下 Kruskal 重构树的形态。在 Kruskal 过程中,若 u,v 同属一个集合说明 u \to v 是环上的一条边。求出 u,v 的代表元 x 以后,单独建一个新点并将 x 挂到儿子上,新点的点权为 (u,v) 的边权。

在查询时,LCA 上方额外多出一个新点,因此环的情形也能被 h_x 修正。这样就做完了,视 n,m,q 同阶复杂度 O(n \log n)。代码。

P2619 [国家集训队] Tree I

给定 n 个点 m 条边的无向带权连通图,每条边有黑白两色。求恰好有 k 条白色边的生成树中,边权和最小的生成树,并输出答案。

:::::success[题解]

我们声称答案关于 k 下凸。

考虑 WQS 二分斜率 a,相当于给每条白边带 +a 的额外代价。此时求出最小生成树中的白边数目,即可决策二分方向。

注意到二分时只要合并黑边和白边两个有序数组,可以归并优化,做到 O(m \alpha(n)\log V)。

类似题目是 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[题解]

对集合 S_i,若 S_i 在 T 上连通,则 S_i 的导出子图必然是一棵树,恰有 |S_i|-1 条边。若导出子图分裂成森林,则边数严格小于 |S_i|-1。

设所有 S_i 导出子图的边数和为 f(T),则 f(T) \le \sum \limits_{i=1}^m (|S_i|-1),当且仅当所有集合均连通时等号成立。

另一方面,记 A_u=\{i \mid u \in S_i\},枚举树边 (u,v),则 (u,v) 对 f(T) 的贡献为 |A_u \cap A_v|。只要最大化 \sum\limits_{(u,v)} |A_u \cap A_v| 并判定这个值是否取等,即可得到构造。

取完全图 K_n,将边 (u,v) 的边权设为 |A_u \cap A_v|,求最大生成树即可。A_u 可以使用 bitset 优化,总复杂度 O\left(\dfrac{n^3}{w}\right)。代码。

:::::

CF1325F Ehab's Last Theorem

给出一个 n 个点 m 条边的连通无向图,找到一个大小为 \lceil\sqrt{n}\rceil 的独立集,或者一个大小不小于 \lceil\sqrt{n}\rceil 的环,输出构造。

:::::success[题解] 考虑拉出一棵 DFS 生成树,如果存在一条返祖边,其端点深度差 \ge\lceil\sqrt{n}\rceil-1,那么就找到了一个满足要求的环,直接输出即可。

反之考虑按深度模 \lceil\sqrt{n}\rceil-1 分成若干同余类,由于返祖边的性质,这些同余类一定都是独立集。感性理解一下,所有集合中必然存在至少一个满足要求的集合,于是做完了。

复杂度 O(n+m)。代码。

P6954 [NEERC 2017] Connections

给定一张 n 个点 m 条边的强连通有向图,保证 n \ge 4 \land m>2n。你需要保留恰好 2n 条边,使图仍然强连通,输出构造。

多测,\sum m \le 10^5,3 秒,512 MB。

:::::success[题解]

任取一点 x,在正反图上以 x 为根求出两棵外向 DFS 生成树 T_1,T_2。

注意到 e(T_1) 保证 x 可达任意点,e(T_2) 保证任意点可达 x。取 T_1 \cup T_2,从 x 中转则任意点对强连通,边数 2n-2。

复杂度 O(n+m)。代码。

:::::

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[题解]

直观的想法是若 i,j 可以匹配就连边 i\leftrightarrow j,求一般图最大匹配,显然不可做。

进行点边转化,将斜率视作顶点,点视作边。记 u_i=\frac{y_i}{x_i+1},v_i=\frac{y_i+1}{x_i},将输入的每个点都视作 u_i\leftrightarrow v_i 的无向边。那么这张图的线图就是上面那个做法建出来的图。

问题是 L(G) 的最大匹配,转化到 G 上得到如下问题:最多能匹配多少对共顶点的边,每条边只能使用一次。

对 G 的全体连通块考虑,下面设 G 连通。理论上界是 \left\lfloor|E|/2\right\rfloor,我们断言上界可以取到,下面给出构造式证明:

拉出一棵 DFS 树,自底向上贪心。设计函数 dfs(u) 返回 u 子树内,未能匹配的那一条边,都匹配则返回无效值。遍历 u 的出边 e=(u,v),进行讨论:

遍历结束后,将被保留的 e 两两任意配对。显然最终剩余至多 1 条边,作为 DFS 的返回值即可。

总复杂度 O(n\log n)。代码。

:::::

P4151 [WC2011] 最大 XOR 和路径

给定 n 个点 m 条边的无向图,边带权。将 1\leadsto n 路径的权值定义为边权异或和,求最大权值。允许多次经过某点或某边。

:::::success[题解]

对于图上的某个环,我们可以在环上绕一圈并原路返回,权值只剩下环的异或和。故任意环的异或和都是可选择的。

下面说明,路径必能表示为任意 1\leadsto n 的路径加上若干个环。

以 1 定根拉出任意 DFS 树,令 d_u 表示 1\to u 的边权异或和。对边 e=(u,v,w) 令 c_e=d_u \oplus w\oplus d_v,表示 1 \leadsto u \to v \leadsto 1 的绕行。

移项得 w=d_u \oplus d_v\oplus c_e。任意 1\leadsto n 的路线 P 展开后,中间节点的 d 成对消去,剩余权值

d_1\oplus d_n\oplus \bigoplus_{e \in P} c_e

合法权值的集合就是 d_n \oplus \text{span}\{c_e\}。对 c_e 建异或线性基即可,复杂度 O(n \log V)。代码。

:::::

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 定理]

考虑降序排序的度数序列 d_1 \sim d_n。若 d_1>n-1 则序列不可简单图化。否则删去 d_1,将接下来 d_1 项各 -1 得到新序列。原序列可简单图化,当且仅当新序列可简单图化。

:::::

:::::info[Erdős-Gallai 定理]

考虑降序排序的度数序列 d_1 \sim d_n,其可简单图化当且仅当满足以下两个条件:

:::::

枚举 d_{n+1} 并利用 Erdős-Gallai 判定,可以做到 O(n^2) 的复杂度。具体地,我们顺次扫描 k,并维护指针 p 表示 d_p \ge k 且最大的 p。则 \sum \limits_{i=k+1}^n \min(d_i,k) 可以分成两个部分单独计算。

实际上,定理的成立性关于 d_{n+1} 单调。具体地,当 \sum \limits_{i=1}^k d_i 超过右式时,可以调大 d_{n+1} 使得右式增大,也可以调小 d_{n+1} 使得左式减小。

如果固定调整方向,就可以用二分求出答案的上下界。

根据定理成立的第一个条件,我们可以得到 d_{n+1} 的奇偶性。找到上下界后直接输出一段连续区间即可。

复杂度 O(n\log^2 n),精细实现可以做到 O(n \log n)。代码。

::::::

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}=\bigoplus\limits_{k=1}^n a_k,一次操作的实质是交换 a_i 与 a_{n+1}。

对于位置 i,若 a_i\ne b_i,则必然存在某个时刻,当 a_{n+1}=b_i 时交换 a_i 与 a_{n+1}。在 a_{n+1} 的视角上,它的值由 b_i 突变为 a_i。

这启示我们建图 b_i\to a_i,则一组合法方案相当于从 a_{n+1} 出发,将所有边都遍历一次,因此只要找一条欧拉路径。

同理令 b_{n+1}=\bigoplus\limits_{k=1}^n b_k,有解当且仅当 a_1\sim a_{n+1} 与 b_1\sim b_{n+1} 构成的多重集相等。

对于数值 x,其在图上的入度等于 x 在 a_1\sim a_n 中的出现次数,出度等于 x 在 b_1\sim b_n 的出现次数。不妨将 b_{n+1}\to a_{n+1} 的虚边补上。若有解,则每个节点的入度都等于出度,此时必有欧拉回路存在。

我们顺次扫描 i=1,2,\cdots,n 求出 a_i\ne b_i 的 i 的数目,作为图的边数 |E|。对值域离散化后连边 b_i\to a_i,忽略孤点求得连通块数目 |C|,如下计算答案:

复杂度 O(n\log n)。代码。

:::::

P9731 [CEOI 2023] Balance

给定一个 m\times k 的矩阵,值域为 [1,n]。你需要将每行重排,使得 \forall i\in[1,n],数字 i 在所有列中出现次数的极差不超过 1。输出构造。保证 \mathbf{k} 是 \mathbf{2} 的幂。

:::::success[题解]

考虑 k=2。对于同行的两个数 u_i,v_i,只要考虑重排为 [u_i,v_i] 还是 [v_i,u_i]。

建图 u_i\leftrightarrow v_i 并用边的方向表示决策。则题目的约束转化为每个点的出入度之差 \le1。套路地建超级源点对所有奇度数点连边,跑出一条欧拉回路表示决策即可。可以获得 35pts。

将其推广到一般情形。对列分治,设当前区间为 [l,r],分治中心为 m。我们用上面的算法将数划分到 [l,m] 和 (m,r] 进行归纳构造。

具体地,考虑连边 a_{i,j}\leftrightarrow a_{i,j+m-l+1},其中 i\in[1,m],j\in[l,m]。则边的两个端点必然被划分到两侧,用边的方向表示决策。建超级源点向所有奇度数点连边,跑欧拉回路得到方案后递归。正确性考虑 c\to\lfloor c/2\rfloor 和 c\to\lceil c/2\rceil 时不存在 \ge2 的层。

复杂度 O(mk\log k)。代码。

:::::

P10873 [COTS 2022] 帽子 Šeširi

现有 n 个人头上戴着红色或白色的帽子,每个人只能看到别人的帽子颜色,他们会根据别人的帽子颜色猜测自己头上帽子的颜色。

你需要为每个人构造一组猜测策略,使得对于所有 2^n 种情况都满足以下条件:

  • 设有 b 人戴了白色帽子,其中至少有 \lfloor\frac{b}{2}\rfloor 人猜对自己帽子的颜色。
  • 设有 c 人戴了红色帽子,其中至少有 \lfloor\frac{c}{2}\rfloor 人猜对自己帽子的颜色。

输出构造。

:::::success[题解]

对于所有 2^n 种情况中的其中一种状态 S,我们只改变第 i 个人戴的帽子颜色得到状态 T。那么第 i 个人在 S,T 中获得的信息完全一致,猜测策略也必然一致。

更直观的说,对第 i 个人的决策就是一个二选一:让 S 增加一个猜对的人,还是让 T 增加一个猜对的人。

考虑图论建模,连无向边 S \leftrightarrow T,然后用边的方向表示决策。如果定向为 S \to T,则令 T 增加一个猜对的人,反之同理。另一种理解是,一条边表示了一种冲突关系,两个端点必然一个满足一个不满足。

一个状态下猜对的人就是这个节点的入度。弱化题目的限制,即要求猜对的人数至少为 \lfloor\frac{n}{2}\rfloor。那么建一个虚点向所有奇度数点连边,然后跑出一条欧拉回路,根据边的方向即可得到答案。

回到原题,我们将一个状态拆成两个点 S_0,S_1,用 S_0 的入度表示状态 S 下白帽猜对的人数,S_1 的入度表示红帽猜对的人数。枚举状态对 (S,T),记 S 中第 i 个人为白帽,T 中第 i 个人为红帽,连边 S_0 \leftrightarrow T_1 然后仿照上面的做法跑欧拉回路即可。

复杂度 O(n2^n)。代码。

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[题解]

先尝试分析理论上界。容易用树上差分得到第 i 条边被经过的次数 c_i,分类讨论:

因此,得分的理论上界是

\sum_{i=1}^{n-1}\min(2,c_i)

断言上界可以取到。为了给出构造式证明,必须让 c_i\ge2 的边真正被正反遍历。

考虑对 m 个点对 (u_i,v_i) 建无向边。我们将原题条件强化为,偶度数点度数平衡,奇度数点出入度之差 \le1。

假定所有连通块都是欧拉图,则可以对每个连通块跑出一条欧拉回路,由出入度平衡的性质构造必然合法。

:::::error[错解]{open}

考虑建超级源点对所有奇度数点连边,再跑欧拉回路。

::::info[Hack]

考虑树的结构 1\to2\to3\to4,给出两次游走 (1,3) 和 (2,4)。

建立的虚图边为 (S,1),(S,2),(S,3),(S,4),(1,3),(2,4)。得到欧拉回路 S\to1\to3\to S\to2\to4\to S。

定向方案为 1\to3,2\to4。此时树边 (2,3) 没有产生 2 的得分。

::::

:::::

使用另一种处理奇度数点的手法。注意到对于树上节点 u,虚图中 u 的度数奇偶性,恰好等于树上 u 邻域 c_i 为奇数的数目奇偶性。这启发我们,将所有 c_i 为奇数的树边加入虚图中,这样虚图中所有点的度数就被调整为偶数。

这样调整之后,我们再对每个连通块跑欧拉回路,得到定向方案即可。

复杂度 O(n\log n+m),如果线性 LCA 可以做到 O(n+m)。代码。

::::::

CF555E Case of Computer Network

给出一个 n 个点 m 条边的无向图。给定 k 对节点 (u_i,v_i),你需要将所有边定向,使得任意 u_i \leadsto v_i 可达。判定是否存在可行方案。

:::::success[题解]

Robbins 定理 连通分量可定向为 SCC,当且仅当连通分量是 E-DCC。

对原图缩 E-DCC 得到一棵树。判掉 u_i,v_i 不连通的情形,则 u_i \to v_i 树链上边的方向确定为 \uparrow 或 \downarrow。

使用树上差分标记方向,若某条边同时确定为 \uparrow 和 \downarrow 则无解。

复杂度 O(m+n\log n),瓶颈在 LCA。代码。

:::::

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[题解]

注意到 c \ge \lceil A/2 \rceil。若 u \leadsto v 存在 2 条边不交路径,则可以令每条边分摊不超过 A/2 的额度,中间节点净变化为 0。故 E-DCC 内任意两点必能平衡。

边双缩点,新点权值 b_u 定义为 E-DCC 点权和,转化为树上问题。

对 v \in \text{son}(u) 求得子树权值和 s_v=\sum \limits_{i \in \text{subtree}(v)} b_i,条件 |s_u| \le c(u,v) 是必要的。这个条件也是充分的,自底向上转账即可。

对树一次 DFS 即可判定。总复杂度 O(n+m)。代码。

:::::

P3225 [HNOI2012] 矿场搭建

给定一个 n 个点 m 条边的连通无向图。你需要设置若干关键点,使得任意一个点删掉后,其余点总能到达一个关键点。

输出关键点的最少数目,以及达成此数目的方案数。保证答案 < 2^{64}。

:::::success[题解] 考虑求出所有割点。此时对于一个大小为 k 的 V-DCC:

复杂度 O(n+m)。

QOJ14810 Trajan Algorithm

有错误的求割点「Trajan 算法」,问题在于返祖边转移 \text{low}_u \gets \text{low}_v。给定一张 n 个点 m 条边无向图,出边顺序确定,求会被错判的所有点。

多测,\sum n, \sum m \le 10^6,2 秒,1024 MB。

:::::success[题解]

割点判定定理是 \exists v \in \text{son}(u), \text{dfn}_u \le \text{low}_v。假算令 \text{low} 更小,故只会判漏割点。

考察下图所示的情形:

标准 Tarjan 算法令 \text{low}_x \gets \text{dfn}_a,假算改为 \text{low}_x \gets \text{low}_a。而 a 存在返祖边 a \to 1,于是 \text{low}_a<\text{dfn}_a。假算在 x \to a 处合并,从而

\text{low}_x\le \text{low}_a<\text{dfn}_a

而 DFS 回溯时 \text{low} 沿树边合并,这样 \text{low}_x 一路传回 a 的儿子 c,使得 \text{low}_c<\text{dfn}_a。

在 a 处进行割点判定需要 \text{low}_c\ge \text{dfn}_a,于是 a 作为割点被判漏。综上所述,得到结论

结论 割点 a 被判漏,当且仅当以 a 为根时,a 的每个子树内存在一条指向 a 的返祖边。

等价表述是,a 同时属于 \ge 2 个 V-DCC,这些点双内有 \ge 2 条连向 a 的边。求出所有 V-DCC 后容易判定。

复杂度 O(n+m)。

:::::

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[题解]

时光倒流,将覆盖操作转化为,首次操作后数值固定不变。

不难发现 (1,1) 操作最后做,(2,2) 操作最先做,只需考察 (1,2) 操作的顺序。

不妨设 x_i=1,y_i=2,连边 u_i \to v_i。分析一些特殊情况:

对有向图进行 SCC 缩点,按缩点后拓扑序操作即可。注意零入度 SCC 的根节点尽量选择 (2,2) 操作的点,这样可以让整个分量都是 2。

复杂度 O(n+m)。代码。

:::::

QOJ2214 Link Cut Digraph

维护一张 n 个点初始无边的有向图,进行 m 次加边,每次操作后求出强连通点对数。

:::::success[题解]

设 T(e) 为边 e 出现时刻,f(e) 为边 e=(u,v) 端点 u \leftrightsquigarrow v 强连通的最早时刻。

对时间轴升序扫描,若 f(e) \ge T(e) 则在 f(e) 时刻加入双向边 u \leftrightarrow v。原图 SCC 等效于当前图的连通块,并查集维护 \sum \binom{\text{siz}_i}{2} 即可。

问题转化为求每条边 e 的 f 值。将操作离线后时间轴分治,设分治区间 [l,r],分治中心为 m。

对分治区间上的边 G_1=(V,E_{[l,r]}) 缩 SCC,则 u \leftrightsquigarrow v 在 G_1 中强连通当且仅当 f(e)\le m。取 e \in E 分讨:

每条边 e 只会划分到一侧,从而 \log 层分治树上 \sum |E| \le O(m\log m)。

注意精细实现,只遍历 E_{[l,r]} 端点,用 Tarjan 求 SCC 可以做到 O(|E|) 复杂度。下传右侧边时只关心 SCC 的闭合时刻,故将端点改为 SCC 标号。

总复杂度 O(m \log m)。代码。

:::::

CF1989F Simultaneous Coloring

现有一个 n \times m 的网格,你可以将一列涂黑,或者将一行涂白。

每轮可以同时进行 k 次操作,代价为 [k>1]k^2。对于同时受到两类操作影响的格子,颜色可以自由选定。

进行 q 次操作,给定 (x,y,c),增加一条限制,格子 (x,y) 必须涂成颜色 c。每次操作后,输出满足所有要求的最小代价。

:::::success[题解]

显然行列至多操作一次。设第 i 行的操作时刻为 x_i,第 j 行的操作时刻为 y_j,钦定 (i,j) 为白等价于 x_i \le y_j,为黑等价于 x_i \ge y_j。

考虑用 n+m 个虚点代表行列,边的方向代表偏序关系。若 (i,j) 为白则连边 i \to j+n,为黑则连边 j+n \to i。

分析可得,最优策略一定是对每个 SCC 整体操作,再按缩点后拓扑序依次操作。答案即为所有 SCC 点数平方和。

离线时间轴分治求出每条边的闭合时刻 f(e),对时间轴扫描线,SCC 转化为无向图连通块,并查集胡乱维护即可。

视 n,m,q 同阶复杂度 O(n \log n)。代码。

:::::

P9139 [THUPC 2023 初赛] 喵了个喵 II

给定一个长为 4n 的序列,其中 1\sim n 各出现 4 次。你需要将其划分为两个相等的子序列,输出构造或报告无解。

:::::success[题解]

考虑问题的弱化,即 1 \sim n 各出现 2 次。设数值 i 两次出现的位置为 l_i,r_i,其中 l_i<r_i,则有

结论 无解当且仅当 \exists i \ne j, [l_i,r_i] \subseteq [l_j,r_j]。

1221 和 1212 是很好的例子。如果有解,则只要将 l_i 分为一组,r_i 分为一组。

受上述讨论启发,记数值 i 四次出现的位置依次为 p_{0,i},p_{1,i},p_{2,i},p_{3,i}。讨论可行的划分方式:

实际上,我们只要关注前两种划分方案。设布尔变量 x_i 表示选择何种方案,将 x_i=1 代表的方案写作 [l_{i,1},r_{i,1}], [l_{i,2},r_{i,2}]。根据无解条件,我们添加下列约束:

这是一个 2-SAT 问题。对约束中的 i,j,连边 x_i \to \neg x_j, x_j \to \neg x_i 后缩 SCC,直接做可得到 O(n^2) 复杂度。

转二维平面分析,则 [l_1,r_1]\subseteq [l_2,r_2] 相当于 (l_1,r_1) 落在一个 2-side 矩形内:

可以做主席树优化建图,或者 CDQ 分治套前缀优化建图,Tarjan 求解复杂度 O(n \log n)。CDQ 代码。

不过我们还有一种更聪明的手法,可以使用 Kosaraju 求 SCC,这样只要两次 DFS。考虑这篇文章中提及的技巧,假设节点 u 代表区间 A=[l_1,r_1],我们希望找到 B=[l_2,r_2] 作为 u 的后继节点 v,且 v 未访问。

使用线段树维护左端点 l,节点维护区间内未访问的 r 的最小 & 最大值。若 B \subseteq A 则在 [l_1,r_1] 上查 r_{\min},若 A \subseteq B 则在 [1,l_1] 上查 r_{\max}。访问 B 前将 B 代表的区间删去。

注意两次 DFS 时正反图的对应关系。复杂度仍为 O(n \log n) 但空间线性。代码。

:::::

CF487E Tourists

给定一张 n 个点 m 条边的无向连通图,点带权 w_i。进行 q 次操作:

  • 给定 i,x,令 w_i \gets x。
  • 给定 u,v,查询 u \leadsto v 所有简单路径中,点权 \min 的最小值。

:::::success[题解]

两个 \min 的方向相同,可以去掉一个,问题变为 u \leadsto v 可经点的权值 \min。

建立广义圆方树,转化为单点修改,链 1- 邻域点权 \min。魔怔一点可以毛毛虫剖分维护。

我们将圆点权值挂在邻域方点上,在方点处用 multiset 记最小值,只要使用普通树剖套线段树解决。复杂度 O(q \log^2 n)。

:::::

P4630 [APIO2018] 铁人两项

给定一张 n 个点 m 条边的无向图。对三元组 (s,x,t) 计数,满足存在 s \leadsto t 的简单路径过点 x。

:::::success[题解]

建立原图的广义圆方树,则 x 的数目为 s \to t 毛毛虫的圆点数。

我们将圆点的权值赋为 -1,方点的权值为度数,于是毛毛虫圆点数转化为 s \to t 树链的权值和。

将贡献拆到每个点上,容易求出有多少对 (s,t) 经过该点。

复杂度 O(n+m)。

:::::

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[题解]

性质 有解的必要条件是 G 是边仙人掌。

证明 设简单环 C_1,C_2 公共路径为 P。分别设路径 P,C_1 \setminus P, C_2\setminus P 的边权和为 w_1,w_2,w_3。由约束得

w_1+w_2 \equiv 1 \pmod 2\\ w_2+w_3 \equiv 1 \pmod 2\\ w_1+w_3 \equiv 1 \pmod 2

三式相加得

2(w_1+w_2+w_3) \equiv 1 \pmod 2

左式显然为偶数,矛盾。故原图必为边仙人掌。

建立原图的广义圆方树,并在圆方树上 DP。设 f_{u,S} 表示满足下列条件的最小代价:

设方点 v 传递数组 h_{v,T} 表示,处理子树后父边颜色集合为 T 的最小代价。圆点处的转移是简单的:

f'_{S \cup T} \gets f_{S}+h_{v,T}

为方便书写,定义两个辅助量,对圆点 u

\begin{aligned} A_u(x)&=\min_{S \cup \{x\} \text{ is valid}} f_{u,S}\\ A_u(x,y)&=\min_{S \cup \{x,y\} \text{ is valid}} f_{u,S}\\ \end{aligned}

意义是方点父亲接 1/2 条边的代价。对边仙人掌,方点必定为桥或简单环,下面讨论方点 DP。

若方点 p 代表桥 u \to v,转移是容易的:

h_{p,\{x\}}=x+A_v(x)

若方点 p 代表环 u \to v_1 \to v_2 \to \cdots \to v_k \to u,枚举 w(u,v_1)=a \in \{0,1,2\} 断环为链。做一个线性 DP:

初始 DP 令 f_{u,\varnothing}=0,其余位置 +\infty。所求为 \min\limits_{S} f_{\text{root},S}。

总复杂度 O(|\Sigma|n+m),其中 |\Sigma| 表示状态数和转移数。代码。

:::::

QOJ5407 基础图论练习题

给定一张 n 个节点的竞赛图。对所有点对 (u,v) 求出,翻转边 (u,v) 后 SCC 的数目。

:::::success[题解]

根据 Landau 定理只要求得 f_k=\sum \limits_{i=1}^k d_i-\dbinom{k}{2}=0 的 k 的数目。

::::info[Landau 定理] 引理 竞赛图缩 SCC 后形成链状图,每个拓扑序在前的 SCC 向在后的所有 SCC 连边。

设竞赛图节点 u 的入度为 d_u,将 d_1 \sim d_n 升序排序,定理指出

Landau 定理 \forall k\in [1,n], \sum \limits_{i=1}^k d_i \ge \dbinom{k}{2}。取到等号的 k 构成度数序列的划分,每段都是一个 SCC。

证明 参见 https://www.cnblogs.com/acha/p/9042984.html,此处不再赘述。

设 L_x,R_x 分别为度数 x 在升序序列 d_i 中第一次 / 最后一次出现的位置。每次翻边恰有一对 +1 和 -1,修改度数 x 可以视作修改 L_x 和 R_x。

设修改令 L_a \gets L_a-1, R_b \gets R_b+1 分讨:

对 f 计数后施前缀和即可做到 O(n^2)。代码。

:::::

P3561 [POI 2017] Turysta

给定一张 n 个节点的竞赛图。对于每个点 u 求出从 u 出发的最长简单路径,输出构造。

::::::success[题解]

利用 Landau 定理推论找出所有 SCC 并缩点后,DAG 的形态是链状图。

考虑找出每个 SCC 的哈密顿回路。根据 DAG 的形态,直接取一段后缀的哈密顿回路拼起来,就能构成一条简单路径。

这样,这个问题的做法就显然了:利用 Camion-Moon 定理的构造求得 SCC 的哈密顿回路。对于一点 u,取拓扑序不小于其所在 SCC 的所有哈密顿回路拼起来。

::::info[Redéi 定理 & Camion-Moon 定理] 竞赛图哈密顿路 & 哈密顿回路构造问题。

Redéi 定理 任何一个竞赛图都至少存在一条哈密顿路。

构造 考虑增量构造。假设我们已经排好了 1 \sim k-1 的哈密顿路 u_1 \sim u_{k-1},尝试插入 k。找到一个位置 i 使得 (k,u_i), (u_{i+1},k) \in E,将 k 插入到 u_i,u_{i+1} 之间即可。注意特判放在首尾的情形。

直接模拟的复杂度为 O(n^2)。使用数据结构上二分,可以做到 O(n \log n)。

Camion-Moon 定理 一个竞赛图存在哈密顿回路,当且仅当它是强连通的。

构造 先用 Redéi 定理的构造找出一条哈密顿路,然后在路径上顺序扫描。

想象我们当前位于点 x,左侧已经被折叠成环 c_1 \to c_2 \to \cdots \to c_m \to c_1,右侧还是一条链,链是哈密顿路的一部分。

我们尝试将 x 插入环中。分类讨论:

精细实现复杂度 O(n^2)。

精细实现复杂度 O(n^2)。代码。

::::::

P6790 [SNOI2020] 生成树

给出一张 n 个点 m 条边的无向连通图,保证 G 在删去某条边后是仙人掌。求 G 的生成树数目,对 998244353 取模。

:::::success[题解]

我们声称 G 是广义串并联图。

设计 DP 状态为 f_e 表示 e 边在生成树上的方案数,g_e 表示 e 边不在生成树上的方案数。使用广义串并联图方法进行转移:

复杂度 1log。代码。

::::info[广义串并联图方法] 广义串并联图,GSPG,定义是不存在同胚于 K_4 子图的图。不加证明地,给出如下性质:

在 OI 中,我们最常用的是广义串并联图方法。

如果图是广义串并联图,则可以通过如上三种操作缩为单点。对于一般图,若 m \le n+k,则使用广义串并联图方法后可以得到 n\le 2k, m \le 3k 的图。

实现时,我们用 std::map 维护邻接矩阵,用队列维护度数 \le 2 的点进行搜索。

使用广义串并联图方法的题,难点主要在于设计 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[题解]

结论 行列式在二维差分后不变。

对矩阵 A 做二维差分,一次操作变为 A_{l-1,l-1},A_{r,r} 加 1,A_{l-1,r}, A_{r,l-1} 减 1。

观察 Matrix-Tree 定理的形式,发现度数矩阵减邻接矩阵的系数正好对上,将问题转化为连边 l-1 \leftrightarrow r 的生成树数目。

建图以后,使用和上一题相同的广义串并联图方法,将问题规约到 n \le 600,m \le 900 的子图上。

考虑使用 Matrix-Tree 定理求子图生成树数目。我们要求的是 \sum \limits_{T} \left(\prod\limits_{e \in T} f_e \right)\left(\prod\limits_{e \notin T} g_e \right),将边权赋为 \dfrac{f_e}{g_e} 求出 \sum \limits_{T} \prod\limits_{e \in T} \dfrac{f_e}{g_e} 并将答案乘上 \prod g_e 即可。

在 g_e \equiv 0 时上面的方法会爆掉,即 extra test #2 的 hack。为此,我们需要将 g_e \equiv 0 的必选边缩起来再进行上面的算法。代码。

:::::