基础图论建模问题

· · 算法·理论

前言

图论建模是什么？

简单来说，这是一种通过将题目条件用图上的点和边描述，将非图上问题转化为图上问题，从而得以从图论的角度发掘性质或求解问题的方法。

这种题目有什么特点？

一般会有一些奇怪的限制，自由或者不好处理的操作。

需要什么前置知识？

难度在提高组内，不会出现网络流/广义串并联图等相关知识。掌握提高组大纲内的图论知识即可。

本文的定位？

基础介绍，给出一些难度较低的经典题目，让读者不至于因为“完全没见过类似思路”而丢分。

同时也起到一个抛砖引玉的作用，大家有什么好题也可以交流一下。

各类思路及例题

生成树

树有 n-1 条边。如果见到题目中总共会进行 n-1 次二元操作（通常是每次操作选出两个，删除一个）就可以考虑图论建模，将对操作集合的研究转化为对生成树的研究。

P4826 [USACO15FEB] Superbull S

给定长为 n 的序列 a。每次操作选出两个数 a_i,a_j，获得 a_i \oplus a_j 的分数，然后任选一个数删除。其中 \oplus 表示按位异或操作。

操作到只剩下一个数为止，求最大可能分数。

::::info[题解] 将每个数看作点，$i,j$ 之间连边，边权为 $a_i \oplus a_j$。任意一个操作集合对应图上的一颗生成树，权值为生成树的边权和。求最大生成树即可。 使用 Prim 算法求解最大生成树，时间复杂度 $O(n^2)$。 :::: #### [P7522 ⎌ Nurture ⎌](/problem/P7522) 给定长为 $n$ 的序列 $v$，每次操作从序列中取出两个数 $a,b$，并将 $a-b$ 放回到序列。 重复操作使得序列只剩下一个数，求最后剩下的数的最大值。 $n \le 3\times 10^5$，$|v_i| \le 10^9$。 ::::info[题解] 将每个数看作点，如果取出了 $a,b$ 并放回了 $a-b$，那么连一条有向边 $a \to b$。 那么，任意一个操作序列对应一颗外向树，记根节点深度为 $1$，那么深度为奇数的点贡献为正，深度为偶数的点贡献为负。 特判掉 $n=1$，必然至少存在一个深度为 $1$ 和一个深度为 $2$ 的节点。分别放上序列中最大和最小的值，记为 $x$ 和 $y$。 剩下的数既可以挂在 $x$ 下面贡献为负，也可以挂在 $y$ 下面贡献为正。两种情况取最大值即可。 时间复杂度 $O(n)$。 :::: #### [CF1608C Game Master](/problem/CF1608C) 给定长为 $n$ 的序列 $a,b$。保证每个序列中的数两两不同。 定义一次操作为：选出两个下标 $i,j$，一个序列 $f \in \{a,b\}$ 。如果 $f_i \gt f_j$ 则 $j$ 被删除，否则 $i$ 被删除。被删除的下标不能再被选出。 $n-1$ 次操作后只有一个下标未被删除。你要对每个下标求出，它是否可能在最后未被删除。 $n \le 10^5$，$1 \le a_i,b_i \le 10^9$。 ::::info[题解] 将每个下标看作点。如果 $a_i \gt a_j$ 或 $b_i \gt b_j$，那么连一条 $i \to j$ 的有向边。 连边之后，每个可能的操作序列都可以表示为图上的一颗外向树，根节点即为未被删除的下标。 也就是说，一个下标 $x$ 可能未被删除，等价于在图上存在一颗以 $x$ 为根的外向树。这又等价于从 $x$ 出发能到达所有点。 Tarjan 缩点后统计入度为 $0$ 的强连通分量即可。如果只存在一个 SCC 入度为 $0$，那么其中所有点都可以不被删除。否则入度为 $0$ 的 SCC 大于一个，无解。 还剩一个问题：暴力连边是 $O(n^2)$ 的。但每个点只连向值比它小的点 **且** 我们只关心图的连通性，那么将序列排序后，每个点连向它前一个点即可。 时间复杂度除排序外线性。 :::: ### 最短路 用于最优化问题。分析方法类似于 DP。如果能将问题描述为多个状态，且状态之间可以互相转移，那么就能使用最短路描述。 #### [P1668 [USACO04DEC] Cleaning Shifts S](/problem/P1668) 有 $[1,T]$ 共 $T$ 个整数时段。 有 $n$ 个人，第 $i$ 个人可以在 $[l_i,r_i]$ 这段时段内值班。 你需要选出最少的人，使得每个时段都至少有一个人在值班。 我们希望得到 $O(n+T)$ 的解法。 ::::info[题解] 首先将“每个时段至少有一个人”转化为“每个人只保留区间内一些时段，使每个时段**恰有**一个人”。 然后，我们证明存在一个最优解，使得每个区间只保留一段前缀： :::info[证明] 考虑问题转化前的最优解。显然最优解不存在区间形成包含关系。将所有区间按左端点排序。 对于两个相邻区间 $[l_1,r_1][l_2,r_2]$ 使得 $l_1 \lt l_2 \le r_1 \lt r_2$，我们让 $[l_1,r_1]$ 只保留 $[l_1,l_2-1]$ 的部分。 这样我们就在不改变答案的情况下，调整成了每个区间只保留前缀，且每个时段只被覆盖一次的方案。由于原答案是最优的，调整后的答案也是最优的。 ::: 构建一张图，使得从 $0$ 到 $i$ 的最短路 $dis_i$ 表示恰好覆盖 $[1,i]$ 中所有时段需要的最小人数。 根据上面的结论，朴素的连边方式是对于一个人 $[l_i,r_i]$ 从 $l_i-1$ 向 $[l_i,r_i]$ 中每一个点连边。这样边数是 $O(n^2)$ 级别的，无法接受。 考虑对于 $[l_i,r_i]$，我们只连边 $l_i-1 \to r_i$，边权为 $1$。再对每个 $i \in [1,n]$ 连边 $i \to i-1$，边权为 $0$。 这样建边后，从 $0$ 到 $i$ 的最短路上的所有边权会形如 $1000110000010$，即先走一条向前的边再走若干条向后的边，重复此过程。这相当于我们选择一个区间，再删去它的一段后缀。 需要注意的是，$x \to^{1} y \to^{0} z(z\lt x \lt y)$ 这样的路径是不合法的，但它劣于 $x \to^{0} z$，所以实际上不会出现。 由于图中边权均属于 $\{0,1\}$，使用 01BFS 求解最短路，时间复杂度 $O(n+T)$。 :::: #### [AT_arc084_b [ABC077D] Small Multiple](/problem/AT_arc084_b) 给定一个整数 $k$。求一个 $S$ 使得 $S$ 是 $k$ 的**正整数倍** ，且最小化 $S$ 的数位和。 - 数位和指每一位上的数字之和。例如，$123$ 的数位和是 $1+2+3=6$。 $2 \le k \le 10^5$。 ::::info[题解] 这是一个名为 **同余最短路** 的 Trick。 将 $S$ 是 $k$ 的倍数转化为 $S \bmod k =0$。然后，我们希望求出对于所有 $i \in [0,k-1]$，$S \bmod k=i$ 时 $S$ 的最小数位和。 考虑一个数按位生成的过程。对于任何一个数，我们都可以从一位数开始，多次在它后面加上一位数来生成。例如，$1 \to 11 \to 114 \to 1145$ 这个过程即可生成数字 $1145$。 建立一张图，我们希望到 $i$ 的最短路 $dis_i$ 即为 $S \bmod k=i$ 时 $S$ 数位和的最小值。 根据上面的过程，我们令 $i$ 向 $(10i+j) \bmod k$ 连边，边权为 $j$，其中 $j \in [0,9]$。沿着边前进一步即代表在末尾加入一位数。这样我们会连出 $O(Bk)$ 条边，其中 $B$ 为进制，本题中为 $10$。 尝试通过 DP 中“小步转移”的思想优化边数。具体地，“在末尾加入一个 $i$”可以表示为“先在末尾加入一个 $0$，再将这个数进行 $i$ 次 $+1$”。这样点 $x$ 只需要向 $10x \bmod k$ 和 $(x+1) \bmod k$ 连边，边数优化到了 $O(k)$ 级别。 值得注意的是，执行一个 $\times 10$ 操作后，连续进行 $\ge 10$ 次 $+1$ 操作是不合法的。但这样劣于先进行 $+1$ 再进行 $\times 10$，所以不合法操作不会出现。 由于图中边权均属于 $\{0,1\}$，使用 01BFS 求解最短路，时间复杂度 $O(k)$。 :::: ### 二分图 一种比较明显的特征是，题目中每个元素有**两个**选择。还有可能跟奇偶性之类的东西相关。 不过我没有找到第二类的好题，第一类也只找到一道好题。 #### [P1155 [NOIP 2008 提高组] 双栈排序](/problem/P1155) 给定长为 $n$ 的排列 $p$，有两个栈 $S_1,S_2$ 和一个出栈序列 $a$。 每次操作可以选定一个栈，将 $p$ 的第一个元素入栈，或将栈顶元素弹出并压入出栈序列 $a$。 你的目标是使得最后 $a$ 为升序。 原题需要输出字典序最小方案，这里**只考虑如何判有没有解**。 $n \le 1000$。 ::::info[题解] 把原序列中的数分成两类，第一类进第一个栈，第二类进第二个栈。 可以看出，“两个栈最终都能分别输出有序序列”是“最终能输出有序序列”的充要条件。 因此只需要考虑什么样的数放在同一个栈会产生冲突。 由于最终序列要求升序，那么任何时刻栈内元素必须**由栈顶到栈底递增**。 也就是说，如果有两个数 $x,y$ 要先后进同一个栈且 $x \lt y$，那么“$x$ 出栈”必须发生在“$y$ 进栈”之前。 而上面的条件想要成立，$y$ 后面必须没有比 $x$ 小的元素 $z$，否则 $z$ 出栈必然晚于 $x$ 出栈，序列不有序。**这个条件是无关 $z$ 在哪个栈的**。 那么，下标 $i,j$ 不能在同一个栈中，当且仅当 $i \lt j,p_i \lt p_j$ 且 $\exist k \gt j,p_k < p_i$。预处理后缀最小值，容易在 $O(n^2)$ 的时间内判定所有数对。 对于每一对不能在同一个栈中的 $(i,j)$，我们连边 $i \leftrightarrow j$，那么能完成排序当且仅当图是二分图。 二分图染色检查即可。时间复杂度 $O(n^2)$。 :::: ### 并查集 一般表现为只知道推导关系，不清楚具体数值。同样没找到什么好题。 #### [P8779 [蓝桥杯 2022 省 A] 推导部分和](/problem/P8779) 有一个长为 $n$ 的序列 $A$。你不知道其中的任何数值，但知道其中 $m$ 个区间的和，形如 $(l,r,x)$ 表示 $\sum_{i=l}^r a_i=x$。 有 $q$ 次询问，每次询问一个区间的和是否确定，如果确定还要输出值。 保证数据不出现矛盾。 $n,m,q \le 10^5$。 ::::info[题解] 将区间和改写为前缀和形式，即 $s_r-s_{l-1}=x$。也就是说，我们可以得知 $s_{l-1}$ 和 $s_r$ 的差值。 将所有的 $(l-1,r)$ 连边，那么在同一个连通块中的点我们都可以知道差值。 使用带权并查集维护，询问 $[L,R]$ 区间和时检查 $L-1$ 和 $R$ 是否在同一个连通块即可。 :::: 本来想放 NOI25 D1T3 A 性质平方的部分分，但细想一下主要难度还是在观察性质而不是并查集上，所以就不放了 >_< ### 直接建图观察性质 一般常见的是有序列 $a$，连边 $i \to a_i$。 如果 $a$ 值域为 $[1,n]$，那么每个点出度为 $1$，形成内向基环树森林。 如果 $a$ 是排列，每个点入度和出度都为 $1$，形成若干个环。 当然还有题目直接给出值的性质，对应到图上可能跟图的形态、权值等有关。 #### [AT_arc189_c [ARC189C] Balls and Boxes](/problem/AT_arc189_c) 有 $n$ 个盒子，初始第 $i$ 个盒子有 $a_i$ 个红球和 $b_i$ 个蓝球。 给定两个排列 $p,q$。每次操作可以选择一个数 $i$，将盒子 $i$ 中所有红球放进盒子 $p_i$，所有蓝球放进盒子 $q_i$。 最终的目标是将所有球放进盒子 $X$，求最小操作次数。 $n \le 2\times 10^5$。 ::::info[题解] 先考虑只有红球怎么做。 连边 $i \to p_i$，会形成若干个环。显然所有球都必须在 $X$ 所在的环才有解。 $X \to p_X$ 这条边一定不会被操作，那么环变成一条链。从链上最深的有球的节点一路操作到 $X$ 即可。下面称这个操作序列为该颜色的**最短操作序列**。 扩展到两种颜色，首先考虑不在最短操作序列上的操作的影响。发现是没有影响，因为球只能一步步挪过去，并且不会往回走。 也就是说，**单个颜色的最短操作序列**必须是**最终操作序列**的子序列。 问题转化为给你两个**元素各不重复**的序列，找到最短的序列使得两个序列均为它的子序列。 可以证明，这个问题的答案为**两序列长度之和**减去它们的 $\operatorname{LCS}$ 长度。 :::info[证明] 考虑两序列 $A,B$ 在最终序列 $s$ 内的对应下标序列 $[a_1,a_2\cdots ],[b_1,b_2\cdots ]$，其中有 $s_{a_i}=A_i$，对 $B$ 同理。 不出现在两个序列中的下标都是无用的，可以删去，那么答案为两集合并集的大小。 最小化两集合并集大小，等价于最大化它们的交集大小。 设交集内的元素分别为 $[c_1,c_2,\cdots]$。那么有 $[s_{c_1},s_{c,2}\cdots]$ 既是 $A$ 的子序列又是 $B$ 的子序列。 也就是说，最大化交集大小，等价于最大化这个公共子序列的长度。最大值显然为 $\operatorname{LCS}$ 的长度。 ::: 由于序列中元素各不重复，使用 [P1439 【模板】最长公共子序列](/problem/P1439) 的做法求 $\operatorname{LCS}$ 即可。 时间复杂度 $O(n\log n)$。 :::: #### [CF283C Coin Troubles](/problem/CF283C) 有 $n$ 种物品，第 $i$ 种价值为 $a_i$。 有 $q$ 条限制，形如 $(x,y)$，表示物品 $x$ 的选取数量必须大于物品 $y$ 的选取数量。**保证所有 $x$ 两两不同，所有 $y$ 两两不同**。 每种物品可以无限选择，问你有多少种不同方法选出总价值为 $T$ 的物品，且满足所有限制。对 $10^9+7$ 取模。 $T \le 10^5,q \le n \le 300$。 ::::info[题解] 加粗的限制很奇怪。对所有的限制 $(x,y)$ 连边 $x \to y$（即链头选的最少，链尾选的最多），那么所有点的入度和出度都**至多为 $1$**。 可以发现，在这种度数限制下，连出的图由多个链和环组成。然而，严格大于的限制使得出现环时答案必定为 $0$，那么只用考虑链的情况。 首先链上离链头距离为 $x$ 的节点至少选 $x$ 个，先选掉这部分，之后限制变为大于或等于。 这种捆绑关系可以用前缀和表示。具体地，如果你选择了一个物品 $x$，那么链尾到 $x$ 的所有物品都要多选一个才能满足限制。 更新完权值后跑完全背包即可。时间复杂度 $O(nT)$。 :::: #### [CF1270G Subset with Zero Sum](/problem/CF1270G) 给定长度为 $n$ 的序列 $a$，**保证 $i-n \le a_i \le i-1$。** 找出序列 $a$ 中任意一个和为 $0$ 的非空子集并输出，或报告无解。 $n \le 10^6$。 ::::info[题解] 题目对 $a_i$ 的限制特别奇怪且出现了 $1$ 和 $n$。 尝试移项，得到 $1 \le i-a_i \le n$。连边 $i \to i-a_i$，得到内向基环树森林。 注意到对于任意一个环，点集等于出边指向的点集。也就是说有 $\sum i = \sum (i-a_i)$。可以得到 $\sum a_i=0$。 找到任意一个环并输出即可。时间复杂度 $O(n)$。 :::: ## 结语 文章源码有 7000+ 字符，10 道例题。肝死我了！ 希望本文可以帮你了解图论建模的基本思路，之后面对此类问题可以游刃有余！ 有什么好的题目也欢迎分享！