Spark Special 图论_杨宁远 杂题分析
Date: 2024-07-03
Preface
本文基于杨宁远 @ynycoding 的课件与题单，对省选/NOIP阶段图论的建模方法和解题策略进行总结，以及本阶段常用方法、模型和 Trick。
A. [AGC056C] 0/1 Balanced
[AGC056C] 01 Balanced - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
要求构造字典序最小的长为 \(n\) 的 0/1 字符串 \(s\) 满足 \(m\) 个条件形如 \((l,r)\) ，单个条件表示 \(s[l\dots r]\) 中必须有相同个 0/1。
其中 \(2\le n\le 10^6,1\le m\le 2\times 10^5\) 。
Solution
差分约束
题目中的限制很容易地就能用前缀和表示，我们容易建立这样的差分约束系统：
Def \(S_i\) 代表前 \(i\) 个中 \(1\) 的个数
-
\(\forall (l,r),S_r-S_l=\frac{r-l+1}{2}\)
-
\(\forall i\in[1,n),0\le S_i-S_{i-1}\le 1\)
嗯，但是这样会建立负权边，只能用 SPFA 求解，时间复杂度最坏 \(\mathcal O(n)\)
我们想，如果能够直接一点，每条限制 \(l,r\) 的表示不会与 \(l,r\) 相关，这样边权就大大简化了
于是我们可以考虑定义 \(S_i\) 为前 \(i\) 个中 \(1\) 的个数减去 \(0\) 的个数，这样，第一类条件可以直接用等于表示，第二类条件则变为：\(\forall i\in[1,n),S_i-S_{i-1}\in \{-1,1\}\) 。
差分约束实际上求出的是最大的解，即对于所有 \(a+x\ge b\) 这样的条件，求出的都是刚刚好满足这些条件的解，即对于最严格的限制，满足 \(a+x=b\)
考虑说明不会存在 \(S_i=S_{i-1}\) ，归纳假设 \(\forall j\in[1,i)\) 都满足 \(S_j\neq S_{j-1}\)
若 \(i\) 没有作为第一种事件的 \(r\) ，那么显然不可能存在这种情况。否则，则说明：\(S_l=S_i=S_{i-1} \) ，与归纳假设矛盾。
可以这样理解，这种情况相当于填充空字符，但是如果只填一个肯定是没用的，他也不能帮你构造合法方案，如果填了偶数个空格，不如把靠前的换成 \(0\) 靠后变成 \(1\)
同时，求解出了最大的解，只需要 flip 一下就是最小的解。
Conclusion
本题提示我们：
-
可以利用前缀和建立有关数量的限制
-
尽量简化边权，消除与第三变量相关的因素，直接用等量关系以及固定边权
-
差分约束是求出最大的解
B. [NOI2001] 食物链
P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
现有三种元素 \(A,B,C\) 定义他们之间有关系 \(A\to B,B\to C,C\to A\)
现有 \(n\) 个元素 \(|S|=n,\forall x\in S,x\in \{A,B,C\}\) ，按顺序给出 \(q\) 个语句，每个都是以下的其中一种：
-
给出 \(X,Y\in S\)，指明他们满足 \(X\to Y\)
-
给出 \(X,Y\in S\)，指明他们满足 \(X=Y\)
现求这些语句有几句不合法语句，即应用之后使得不存在一种赋值方案满足前面所有的合法语句
Solution
典中典，并查集
使用扩展域可以很简单地解决问题，现在看看边带权。
采用带权并查集维护与当前父亲的关系，这是一个循环的关系，使用 \(\mathbb F_3\) 关于 \(+\) 形成的群可以维护这个信息。
在合并和路径压缩的时候维护即可。
Conclusion
-
扩展域描述了物体的多个属性
-
边带权可以用来维护与父亲节点的关系
C. CF118E Bertown roads
Problem Statement
给定无向连通图 \(G\) ，现要将 \(G\) 中每条边定向，要求定向后是强连通的，询问是否可能并输出方案。
Solution
注意到原图只要是边双连通的即可，原因是，如果建立 dfs 树，在任何一个点只沿着返祖边往上爬一定能够回到根节点，否则在无法这样做的地方必然形成桥，这也给出了构造方案。
Conclusion
-
基于 dfs 树深度优先的性质，事实上，无向图的 dfs 树上的非树边没有横叉边。
-
基于上述性质，利用 dfs 树的深度以及 dfn 序来解决一些与连通性有关的问题非常有用，例如 图上二选一构造问题
-
Tarjan 利用追溯值来处理能够到达的祖先，来确定子树是否封闭（存在环），我们可以通过维护一个栈，在 \(low[x]=dfn[x]\) 时及时弹出来求出 \(\mathbf{eDCC}\)
D. 最大 XOR 和路径
P4151 [WC2011] 最大XOR和路径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
给定带权无向连通图 \(G\)，请求出一条路径 \(P(1\to n)\) 使得对于路径上的点 \(p_1,p_2,p_3,\dots,p_n\) ，其中 \(p_1=1,p_n=n\) ，最大化 \(\bigoplus\limits_{i\in[1,n)}w(p_i\to p_{i+1})\)
Solution
思维，线性基，DFS树
这是一个好题，需要挖掘一些性质。
不难注意到以下事实：
-
必选一条 \(1\to n\) 的简单路径和若干简单环（从 \(1\) 出发可达的）
-
这一条简单路径可以随便选
那么只需要在 dfs 树上维护前缀异或值，遇返祖边直接在线性基里加入该环。
Conclusion
-
可先从简单的情况开始寻找性质，例如右图
-
然后加入环套环这样的情况进一步寻找性质
-
dfs 树可以用来找到简单环
E. Edges in MST
Problem Statement
给定一个带正权无向连通图 \(G\) ，求每条边是否是：最小生成树的必须边/可行边
Solution
思维，Tarjan，并查集
考虑替换 MST 形成新的 MST，发现只有边权相等的边才能互相替换，但是这样想是不方便进行维护的（您需要路径修改相等边集合）。
考虑构造性的思路，在 Kruskal 算法构造 MST 的时候，对于所有边权相等的边 \(u_1,u_2,\dots,u_m\) ，如果 \(u_i\) 两边已经连通，则是不可能边，否则，加入图中跑 Tarjan，如果是桥边，说明这是一条必须边，否则是可行边。
Conclusion
-
对于最小生成树问题，可以考虑三种思路：
-
替换边思路
-
边贪心构造思路（Kruskal、Boruvka）
-
MST 扩展思路（Prim）
-
F. Tourists
Problem Statement
给定无向连通图 \(G\)，点带权，要求支持如下两种操作：1. 单点修改点权 2. 求 \(a\to b\) 所有简单路径上最小点权的最小值
Solution
圆方树，树链剖分，Tarjan
我们维护的是无向图上的简单路径信息，而且还是路径最小值，我们想想简单路径的构成，可以发现，如果一条路径走入一个点双，那么我们就可以访问点双的任何一个点，然后从任何地方出来，这样，点双内部怎么走我们就不需要知道，所以我们干脆把点双压成一个点，然后修改的时候改归属即可。
如果你这么想了，那么恭喜！如果当年是你在 WC，那么发明 圆方树 的人就是你了。
那么建立圆方树，用 multiset 维护与方点相连的点的权值，树链剖分建线段树求最小值即可
Conclusion
-
圆方树主要是注意到维护的路径信息可以在点双里压缩
-
维护无向图的路径，优先考虑圆方树，其次可以考虑在生成树上处理（如 dfs 树）
G. Too Many Constraints
Problem Statement
要求你求出序列 \(a_1,a_2,\dots,a_n\)，要求满足若干限制：
-
\(\forall i\in[1,n),a_i\le a_{i+1}\)
-
\(\forall i\in[1,n],a_i\in [1,k]\cap \mathbb Z\)
-
若干句要求，每条形如，\(a_i\neq x\)
-
若干句要求，每条形如，\(a_i+a_j\le x\)
-
若干句要求，每条形如，\(a_i+a_j\ge x\)
输出方案，或者报告无解。
Solution
2-SAT
这种约束容易让人想到差分约束，但是回顾一下三角形不等式的形状，我们发现变量前面带系数，这是不可以的。
我们发现 \(k\) 没有多大，显然每一个取值是否可以是很容易确认的，每一条要求都是在值域上面的一个限制，都是可以转化为要求值域小于/大于一个值，我们发现这是不错的。在应用了所有条件以后，我们要确定变量的值域，所以我们可以把 \(k\) 个取值都建立出来，每个条件就会排除其中一些，我们发现限制的后两者说的就是 如果 \(a_i\) 取到 \(p\) 那么 \(a_j\) 就必须取 \(\le x-p\) 的那些。
我们发现，如果ai取值p则bi取值q 很类似 2-SAT，可以将每个变量建立成一个变量，表示选或者不选。欸，问题来了，怎么保证一个变量选且仅选一个值呢？
所以这样是不行的，这几个变量之间太独立了，2-SAT 只能保证最多一个点选，无法保证一定有一个点被选，这时候，我们可以把变量的要求改为 \(x_i\) 是否 \(\le k\) ，这样的好处是，我们可以通过钦定 “如果 \(x_i\) 不是 \(\le k\) 的，那么就必须 \(\le k\)” 来钦定它必选。其他的很简单，请自己补全。
Conclusion
- 本题为我们提供了变量值域限制问题的新解法，通过拆值域建立 \(\le\) 来进行 2-SAT
H. 序列
#3629. 「2021 集训队互测」序列 - 题目 - LibreOJ (loj.ac)
Problem Statement
要求构造序列 \(a_1,a_2,\dots,a_n\) ，满足以下限制：
-
\(\forall i\in [1,n],a_i\in [1,10^9]\)
-
\(m\) 个这样的限制： \(a_i+a_j+a_k-\max(a_i,a_j,a_k)-\min(a_i,a_j,a_k)=x_i\)
输出方案，或者报告无解。
Solution
2-SAT
注意到第二个信息是指 \(a_i,a_j,a_k\) 的中位数必须是 \(x\)
那么我们发现，要使得中位数为 \(x\) ，则至多只能存在一个数大于 \(x\)，至多只能存在一个值小于 \(x\)，这样剩下的那个数显然就即不能大于 \(x\) 又不能小于 \(x\)，就只能为 \(x\)，这样就可以了。
这就很想上一个题目，但是，这值域太大了吧？但是一想，用到的信息其实没有那么多，大部分值域都没有用。我们考虑简化值域的方法即离散化，这个题能不能离散化呢？
可以！考虑若对于信息 \((a_i,a_j,a_k,x)\) ，对于其中确定为中位数的那个，只能选择 \(x\)，对于其中不为中位数的其余两个数，例如若 \(a_i\le x\) ，且在最后方案里面 \(a_i\notin \{x_k\vert k\in[1,m]\}\) ，我们考虑这种方案可以被替换成其他的限制的元素（您可以模拟一下不同情况）。
那么我们直接离散化即可。
Conclusion
-
对于取值限制问题，应该尽量思考每个变量的取值对于其他变量有什么影响
-
对于取值限制问题，尽量减小每个变量的值域
I. Flip and Reverse
Skipped, TBD
J. Red-Blue Graph
Skipped, TBD
K. 圆桌问题
P3254 圆桌问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
现有 \(m\) 种不同颜色的球每一种 \(r_i\) 个，有 \(n\) 个盒子每个容量不同分别是 \(c_i\)，要求将所有球分配到盒子里，要求每个盒子里不能包含相同颜色的球，输出任何一个方案或者报告无解。
Solution
网络流
网络流的题目没有很明显的特征，但是本题数据范围很小，可以考虑。
我们可称本题的模型为 选择贡献-数量限制模型
建立要进行数量限制的单元，本题有三种数量限制：
-
球数限制
-
容量限制
-
贡献数量限制
提取并建立
Conclusion
选择贡献-数量限制模型应该准确提取对题目中元素的限制是什么，把限制的提供者和贡献的流向建出来
L. 蜥蜴
P2472 [SCOI2007] 蜥蜴 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃 到边界外。
每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。
石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。
Solution
网络流，最大流
本题和上面那个题的模型是一样的，直接建图即可，不再赘述。
M. 魔术球问题
P2765 魔术球问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 \(1,2,3,\dots\) 的球。
- 每次只能在某根柱子的最上面放球。
- 在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在 n 根柱子上最多能放多少个球。
Solution
最大流
其实此题和前面的模型也是一样的，但是有一点不同的
此处我们最大流的含义是，前面最多少开几个柱子，即最多合并几次，每一次加一个数 \(x\)，加边 \(S\to in_x,out_x\to T\) ，对于所有 \(y<x,x+y=a^2,a\in\mathbb N^*\) ，加边 \(in_y\to out_x\) ，即可以把 \(y\) 整个接到 \(x\) 后面，节省了一个柱子。
网络流是一种会调整之前流量的算法，故在残量网络上跑最大流的过程包含了进行退流和重新推流的过程，前者表示拆分一个已经合并的柱子，取消之前的一次合并，后者表示进行一次合并。
Conclusion
-
最小消耗可以转化为最大节省，常常是最大化合并
-
利用网络流的退流，要处理有顺序的问题时，可以依次加入点，然后再残量网络上跑最大流即可
N. 危桥
P3163 [CQOI2014] 危桥 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Solution
本题比较玄学，要求强大的注意力，笔者也没有这样的注意力，遇到这种题只能自认倒霉。
P3163 [CQOI2014] 危桥 题解 - 洛谷专栏 (luogu.com)
Conclusion
没有
O. Bricks
Problem Statement
你有一个 \(n\times m\)（\(1\le n,m\le 200\)）的格子纸，格子要么涂黑（#）要么涂白（.）。你需要用若干个长为一，宽为任意正整数或者宽为一，长为任意正整数的长方形去覆盖所有黑色格子，要求不能盖到白色格子上，不能盖到其他长方形上，不能盖出格子纸的边界，求最少用多少个长方形。
数据保证至少有一个黑色格子。
Solution
最大流，二分图，最大匹配，最大独立集，最小割
本题与 M 题类似，都是要最小化一个花费，我们发现可以把两块相连同向的木板连成一块，这启发我们用上面同样的方式，我们在两个单元格之间建立一个点，我们发现，如果一个格子上/下面的点和左/右边的点同时被选，则是不合法的，所有我们把所有上下的点放在二分图左部，左右的点放在右边，中间不能同时选的连边，此时答案就等于二分图的最大独立集。
Conclusion
我们有必要查看几个常用结论
-
最大流=二分图最大匹配=最小割=最小点覆盖
-
补图的最大独立集等于原图最大团
-
n-二分图最大匹配=n-二分图最小点覆盖=n-二分图最小割=最大独立集
-
DAG的最小路径点覆盖=n-拆点二分图的最大匹配，最小路径可重复点覆盖可先传递闭包再做普通最小路径点覆盖
-
本题用到的结论可以通过构建一个图跑最小割证明，即 n-二分图最小割=最大独立集
P. 文理分科
P4313 文理分科 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
小 P 所在的班级可以用一个 \(n\times m\) 的矩阵进行描述。现每人必须从文科和理科中选择一科。选择科目会获得一个满意值：
-
如果第 \(i\) 行第 \(j\) 列的同学选择了文科，则他将获得 \(art_{i,j}\) 的满意值，如果选择理科，将得到 \(science_{i,j}\) 的满意值。
-
如果第 \(i\) 行第 \(j\) 列的同学选择了文科，并且他相邻（四连通）的同学全部选择了文科，会增加 \(same\text{\underline{ }}art_{i,j}\) 的满意值。
-
如果第 \(i\) 行第 \(j\) 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 \(same\text{\underline{ }}science_{i,j}\) 的满意值。
求最大满意值之和。
Solution
最小割
这是一种新的最小割模型 ，我们知道最小割这种东西就是用来计算代价的。那么我们不妨假设全部贡献都已经获得，对于每一个人，显然只能选择一科，不妨表示为 0/1，则问题变为一个变量取值的问题。现在考虑怎么限制条件二三。考虑新建一个节点，把它与所有牵涉到的人连一条 \(+\infty\) 的边，然后连到原点，权为对应的 \(same\_xxx\) 贡献。
Conclusion
-
最小割是用来计算代价的，假设全部贡献已经获得就可以化为最小割
-
不妨考虑如果不满足要求，怎么样才可以阻碍这种情况形成，除非放弃贡献，支付代价。
Q. 切糕
P3227 [HNOI2013] 切糕 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
有一个 \(n\times m\) 的矩阵 \(a_{i,j}\in [1,R]\) ，每个位置及这个位置的数合起来有一个权值 \(v(i,j,a_{i,j})\) 。现在给出这个所有的权值 \(v\) ,求满足相邻位置（上下左右）的值之差 \(\le D\) 这一限制的情况下，权值和最小是多少，即使得 \(\sum_{x,y}v(x,y,a_{x,y})\) 最小。
\(1\le n,m,R\le 40,0\le D\le R\)
Acknowledgement: @lupengheyyds
Solution
最小割
本题即切糕模型，用于解决离散变量取值问题，不同取值有一个贡献，而不同变量之间又有限制，形式常为变量差/和大于/小于给定值。
此时我们建立一条链，表示所有可能取值，割掉即表示选择这个取值（如何保证只取一个？代价非负），然后尝试阻碍不合法的情况形成，只需要向对应的变量连边。
R. 狼抓兔子
P4001 [ICPC-Beijing 2006] 狼抓兔子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
即给定一个加上所有左上到右下斜边的网格图，求最小割。
Solution
最小割，平面图
重要定理：平面图最小割等于其对偶图的最短路
S. Starry Night Camping
Starry Night Camping - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Skipped, TBD
T. 太空飞行计划问题
最小割
比较简单，跳过
U. order
是上面那个的推广，也比较简单。
V. Dominance
把坐标系转 45° 然后就变成扫描线。
Postscript
啊啊啊啊啊写完了
感受思维的脉搏
标签：md,le,最小,Solution,Statement,Spark,杂题,Problem,Conclusion From： https://www.cnblogs.com/haozexu/p/18288958