专栏文章

基础图论建模问题

xxxsevenWishBloom
算法·理论参与者 11已保存评论 15

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@mi4d8w4i
此快照首次捕获于
2025/11/18 17:23
3 个月前
此快照最后确认于
2025/12/02 00:06
3 个月前
查看原文

前言

图论建模是什么？

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

这种题目有什么特点？

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

需要什么前置知识？

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

本文的定位？

基础介绍，给出一些难度较低的经典题目，让读者不至于因为“完全没见过类似思路”而丢分。
同时也起到一个抛砖引玉的作用，大家有什么好题也可以交流一下。

各类思路及例题

生成树

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

P4826 [USACO15FEB] Superbull S

给定长为 nn 的序列 aa。每次操作选出两个数 ai,aja_i,a_j，获得 ai⊕aja_i \oplus a_j 的分数，然后任选一个数删除。其中 ⊕\oplus 表示按位异或操作。
操作到只剩下一个数为止，求最大可能分数。
n≤2000n \le 2000，1≤ai≤230−11\le a_i \le 2^{30}-1。
题解
将每个数看作点，i,ji,j 之间连边，边权为 ai⊕aja_i \oplus a_j。任意一个操作集合对应图上的一颗生成树，权值为生成树的边权和。求最大生成树即可。
使用 Prim 算法求解最大生成树，时间复杂度 O(n2)O(n^2)。

P7522 ⎌ Nurture ⎌

给定长为 nn 的序列 vv，每次操作从序列中取出两个数 a,ba,b，并将 a−ba-b 放回到序列。
重复操作使得序列只剩下一个数，求最后剩下的数的最大值。
n≤3×105n \le 3\times 10^5，∣vi∣≤109|v_i| \le 10^9。
题解
将每个数看作点，如果取出了 a,ba,b 并放回了 a−ba-b，那么连一条有向边 a→ba \to b。
那么，任意一个操作序列对应一颗外向树，记根节点深度为 11，那么深度为奇数的点贡献为正，深度为偶数的点贡献为负。
特判掉 n=1n=1，必然至少存在一个深度为 11 和一个深度为 22 的节点。分别放上序列中最大和最小的值，记为 xx 和 yy。
剩下的数既可以挂在 xx 下面贡献为负，也可以挂在 yy 下面贡献为正。两种情况取最大值即可。
时间复杂度 O(n)O(n)。

CF1608C Game Master

给定长为 nn 的序列 a,ba,b。保证每个序列中的数两两不同。
定义一次操作为：选出两个下标 i,ji,j，一个序列 f∈{a,b}f \in \{a,b\} 。如果 fi>fjf_i \gt f_j 则 jj 被删除，否则 ii 被删除。被删除的下标不能再被选出。
n−1n-1 次操作后只有一个下标未被删除。你要对每个下标求出，它是否可能在最后未被删除。
n≤105n \le 10^5，1≤ai,bi≤1091 \le a_i,b_i \le 10^9。
题解
将每个下标看作点。如果 ai>aja_i \gt a_j 或 bi>bjb_i \gt b_j，那么连一条 i→ji \to j 的有向边。
连边之后，每个可能的操作序列都可以表示为图上的一颗外向树，根节点即为未被删除的下标。
也就是说，一个下标 xx 可能未被删除，等价于在图上存在一颗以 xx 为根的外向树。这又等价于从 xx 出发能到达所有点。
Tarjan 缩点后统计入度为 00 的强连通分量即可。如果只存在一个 SCC 入度为 00，那么其中所有点都可以不被删除。否则入度为 00 的 SCC 大于一个，无解。
还剩一个问题：暴力连边是 O(n2)O(n^2) 的。但每个点只连向值比它小的点 且 我们只关心图的连通性，那么将序列排序后，每个点连向它前一个点即可。
时间复杂度除排序外线性。

最短路

用于最优化问题。分析方法类似于 DP。如果能将问题描述为多个状态，且状态之间可以互相转移，那么就能使用最短路描述。

P1668 [USACO04DEC] Cleaning Shifts S

有 [1,T][1,T] 共 TT 个整数时段。
有 nn 个人，第 ii 个人可以在 [li,ri][l_i,r_i] 这段时段内值班。
你需要选出最少的人，使得每个时段都至少有一个人在值班。
我们希望得到 O(n+T)O(n+T) 的解法。
题解
首先将“每个时段至少有一个人”转化为“每个人只保留区间内一些时段，使每个时段恰有一个人”。
然后，我们证明存在一个最优解，使得每个区间只保留一段前缀：
证明
考虑问题转化前的最优解。显然最优解不存在区间形成包含关系。将所有区间按左端点排序。
对于两个相邻区间 [l1,r1][l2,r2][l_1,r_1][l_2,r_2] 使得 l1<l2≤r1<r2l_1 \lt l_2 \le r_1 \lt r_2，我们让 [l1,r1][l_1,r_1] 只保留 [l1,l2−1][l_1,l_2-1] 的部分。
这样我们就在不改变答案的情况下，调整成了每个区间只保留前缀，且每个时段只被覆盖一次的方案。由于原答案是最优的，调整后的答案也是最优的。
构建一张图，使得从 00 到 ii 的最短路 disidis_i 表示恰好覆盖 [1,i][1,i] 中所有时段需要的最小人数。
根据上面的结论，朴素的连边方式是对于一个人 [li,ri][l_i,r_i] 从 li−1l_i-1 向 [li,ri][l_i,r_i] 中每一个点连边。这样边数是 O(n2)O(n^2) 级别的，无法接受。
考虑对于 [li,ri][l_i,r_i]，我们只连边 li−1→ril_i-1 \to r_i，边权为 11。再对每个 i∈[1,n]i \in [1,n] 连边 i→i−1i \to i-1，边权为 00。
这样建边后，从 00 到 ii 的最短路上的所有边权会形如 10001100000101000110000010，即先走一条向前的边再走若干条向后的边，重复此过程。这相当于我们选择一个区间，再删去它的一段后缀。
需要注意的是，x→1y→0z(z<x<y)x \to^{1} y \to^{0} z(z\lt x \lt y) 这样的路径是不合法的，但它劣于 x→0zx \to^{0} z，所以实际上不会出现。
由于图中边权均属于 {0,1}\{0,1\}，使用 01BFS 求解最短路，时间复杂度 O(n+T)O(n+T)。

AT_arc084_b [ABC077D] Small Multiple

给定一个整数 kk。求一个 SS 使得 SS 是 kk 的正整数倍 ，且最小化 SS 的数位和。
  • 数位和指每一位上的数字之和。例如，123123 的数位和是 1+2+3=61+2+3=6。
2≤k≤1052 \le k \le 10^5。
题解
这是一个名为 同余最短路 的 Trick。
将 SS 是 kk 的倍数转化为 S mod k=0S \bmod k =0。然后，我们希望求出对于所有 i∈[0,k−1]i \in [0,k-1]，S mod k=iS \bmod k=i 时 SS 的最小数位和。
考虑一个数按位生成的过程。对于任何一个数，我们都可以从一位数开始，多次在它后面加上一位数来生成。例如，1→11→114→11451 \to 11 \to 114 \to 1145 这个过程即可生成数字 11451145。
建立一张图，我们希望到 ii 的最短路 disidis_i 即为 S mod k=iS \bmod k=i 时 SS 数位和的最小值。
根据上面的过程，我们令 ii 向 (10i+j) mod k(10i+j) \bmod k 连边，边权为 jj，其中 j∈[0,9]j \in [0,9]。沿着边前进一步即代表在末尾加入一位数。这样我们会连出 O(Bk)O(Bk) 条边，其中 BB 为进制，本题中为 1010。
尝试通过 DP 中“小步转移”的思想优化边数。具体地，“在末尾加入一个 ii”可以表示为“先在末尾加入一个 00，再将这个数进行 ii 次 +1+1”。这样点 xx 只需要向 10x mod k10x \bmod k 和 (x+1) mod k(x+1) \bmod k 连边，边数优化到了 O(k)O(k) 级别。
值得注意的是，执行一个 ×10\times 10 操作后，连续进行 ≥10\ge 10 次 +1+1 操作是不合法的。但这样劣于先进行 +1+1 再进行 ×10\times 10，所以不合法操作不会出现。
由于图中边权均属于 {0,1}\{0,1\}，使用 01BFS 求解最短路，时间复杂度 O(k)O(k)。

二分图

一种比较明显的特征是，题目中每个元素有两个选择。还有可能跟奇偶性之类的东西相关。
不过我没有找到第二类的好题，第一类也只找到一道好题。

P1155 [NOIP 2008 提高组] 双栈排序

给定长为 nn 的排列 pp，有两个栈 S1,S2S_1,S_2 和一个出栈序列 aa。
每次操作可以选定一个栈，将 pp 的第一个元素入栈，或将栈顶元素弹出并压入出栈序列 aa。
你的目标是使得最后 aa 为升序。
原题需要输出字典序最小方案，这里只考虑如何判有没有解。
n≤1000n \le 1000。
题解
把原序列中的数分成两类，第一类进第一个栈，第二类进第二个栈。
可以看出，“两个栈最终都能分别输出有序序列”是“最终能输出有序序列”的充要条件。
因此只需要考虑什么样的数放在同一个栈会产生冲突。
由于最终序列要求升序，那么任何时刻栈内元素必须由栈顶到栈底递增。
也就是说，如果有两个数 x,yx,y 要先后进同一个栈且 x<yx \lt y，那么“xx 出栈”必须发生在“yy 进栈”之前。
而上面的条件想要成立，yy 后面必须没有比 xx 小的元素 zz，否则 zz 出栈必然晚于 xx 出栈，序列不有序。这个条件是无关 zz 在哪个栈的。
那么，下标 i,ji,j 不能在同一个栈中，当且仅当 i<j,pi<pji \lt j,p_i \lt p_j 且 ∃k>j,pk<pi\exist k \gt j,p_k < p_i。预处理后缀最小值，容易在 O(n2)O(n^2) 的时间内判定所有数对。
对于每一对不能在同一个栈中的 (i,j)(i,j)，我们连边 i↔ji \leftrightarrow j，那么能完成排序当且仅当图是二分图。
二分图染色检查即可。时间复杂度 O(n2)O(n^2)。

并查集

一般表现为只知道推导关系，不清楚具体数值。同样没找到什么好题。

P8779 [蓝桥杯 2022 省 A] 推导部分和

有一个长为 nn 的序列 AA。你不知道其中的任何数值，但知道其中 mm 个区间的和，形如 (l,r,x)(l,r,x) 表示 ∑i=lrai=x\sum_{i=l}^r a_i=x。
有 qq 次询问，每次询问一个区间的和是否确定，如果确定还要输出值。
保证数据不出现矛盾。
n,m,q≤105n,m,q \le 10^5。
题解
将区间和改写为前缀和形式，即 sr−sl−1=xs_r-s_{l-1}=x。也就是说，我们可以得知 sl−1s_{l-1} 和 srs_r 的差值。
将所有的 (l−1,r)(l-1,r) 连边，那么在同一个连通块中的点我们都可以知道差值。
使用带权并查集维护，询问 [L,R][L,R] 区间和时检查 L−1L-1 和 RR 是否在同一个连通块即可。
本来想放 NOI25 D1T3 A 性质平方的部分分，但细想一下主要难度还是在观察性质而不是并查集上，所以就不放了 >_<

直接建图观察性质

一般常见的是有序列 aa，连边 i→aii \to a_i。
如果 aa 值域为 [1,n][1,n]，那么每个点出度为 11，形成内向基环树森林。
如果 aa 是排列，每个点入度和出度都为 11，形成若干个环。
当然还有题目直接给出值的性质，对应到图上可能跟图的形态、权值等有关。

AT_arc189_c [ARC189C] Balls and Boxes

有 nn 个盒子，初始第 ii 个盒子有 aia_i 个红球和 bib_i 个蓝球。
给定两个排列 p,qp,q。每次操作可以选择一个数 ii，将盒子 ii 中所有红球放进盒子 pip_i，所有蓝球放进盒子 qiq_i。
最终的目标是将所有球放进盒子 XX，求最小操作次数。
n≤2×105n \le 2\times 10^5。
题解
先考虑只有红球怎么做。
连边 i→pii \to p_i，会形成若干个环。显然所有球都必须在 XX 所在的环才有解。
X→pXX \to p_X 这条边一定不会被操作，那么环变成一条链。从链上最深的有球的节点一路操作到 XX 即可。下面称这个操作序列为该颜色的最短操作序列。
扩展到两种颜色，首先考虑不在最短操作序列上的操作的影响。发现是没有影响，因为球只能一步步挪过去，并且不会往回走。
也就是说，单个颜色的最短操作序列必须是最终操作序列的子序列。
问题转化为给你两个元素各不重复的序列，找到最短的序列使得两个序列均为它的子序列。
可以证明，这个问题的答案为两序列长度之和减去它们的 LCS⁡\operatorname{LCS} 长度。
证明
考虑两序列 A,BA,B 在最终序列 ss 内的对应下标序列 [a1,a2⋯ ],[b1,b2⋯ ][a_1,a_2\cdots ],[b_1,b_2\cdots ]，其中有 sai=Ais_{a_i}=A_i，对 BB 同理。
不出现在两个序列中的下标都是无用的，可以删去，那么答案为两集合并集的大小。
最小化两集合并集大小，等价于最大化它们的交集大小。
设交集内的元素分别为 [c1,c2,⋯ ][c_1,c_2,\cdots]。那么有 [sc1,sc,2⋯ ][s_{c_1},s_{c,2}\cdots] 既是 AA 的子序列又是 BB 的子序列。
也就是说，最大化交集大小，等价于最大化这个公共子序列的长度。最大值显然为 LCS⁡\operatorname{LCS} 的长度。
由于序列中元素各不重复，使用 P1439 【模板】最长公共子序列 的做法求 LCS⁡\operatorname{LCS} 即可。
时间复杂度 O(nlog⁡n)O(n\log n)。

CF283C Coin Troubles

有 nn 种物品，第 ii 种价值为 aia_i。
有 qq 条限制，形如 (x,y)(x,y)，表示物品 xx 的选取数量必须大于物品 yy 的选取数量。保证所有 xx 两两不同，所有 yy 两两不同。
每种物品可以无限选择，问你有多少种不同方法选出总价值为 TT 的物品，且满足所有限制。对 109+710^9+7 取模。
T≤105,q≤n≤300T \le 10^5,q \le n \le 300。
题解
加粗的限制很奇怪。对所有的限制 (x,y)(x,y) 连边 x→yx \to y（即链头选的最少，链尾选的最多），那么所有点的入度和出度都至多为 11。
可以发现，在这种度数限制下，连出的图由多个链和环组成。然而，严格大于的限制使得出现环时答案必定为 00，那么只用考虑链的情况。
首先链上离链头距离为 xx 的节点至少选 xx 个，先选掉这部分，之后限制变为大于或等于。
这种捆绑关系可以用前缀和表示。具体地，如果你选择了一个物品 xx，那么链尾到 xx 的所有物品都要多选一个才能满足限制。
更新完权值后跑完全背包即可。时间复杂度 O(nT)O(nT)。

CF1270G Subset with Zero Sum

给定长度为 nn 的序列 aa，保证 i−n≤ai≤i−1i-n \le a_i \le i-1。
找出序列 aa 中任意一个和为 00 的非空子集并输出，或报告无解。
n≤106n \le 10^6。
题解
题目对 aia_i 的限制特别奇怪且出现了 11 和 nn。
尝试移项，得到 1≤i−ai≤n1 \le i-a_i \le n。连边 i→i−aii \to i-a_i，得到内向基环树森林。
注意到对于任意一个环，点集等于出边指向的点集。也就是说有 ∑i=∑(i−ai)\sum i = \sum (i-a_i)。可以得到 ∑ai=0\sum a_i=0。
找到任意一个环并输出即可。时间复杂度 O(n)O(n)。

结语

文章源码有 7000+ 字符，10 道例题。肝死我了！
希望本文可以帮你了解图论建模的基本思路，之后面对此类问题可以游刃有余！
有什么好的题目也欢迎分享！

评论

共 15 条评论，欢迎与作者交流。

正在加载评论...