大卫信奥 · 2026 国庆集训

模拟赛 + 专题课

三天，每天先花 1 小时复盘模拟赛，再用 1.5 小时讲一个专题。

← 返回主页

课程目录

三天，从搜索走到图论

01

搜索与暴力

Day3 · 暴力骗分与搜索

A 先把能拿的分拿干净 —— 子任务、特殊性质、打表

B 搜得完，也要剪得掉 —— 剪枝、加深、折半

C 队列一开，最短路自己长出来 —— 网格/多源/状态/双向

02

图论与树论（上）

Day4 · 图论与最短路

A 边权只剩两种值的时候 —— 0-1 BFS

B 一个三重循环，三种用法 —— Floyd 的三个视角

C 倒着搜一次，正着数一遍 —— 反图与最短路计数

03

图论与树论（下）

Day5 · 并查集与分层图

A 从“连不连通”到“差多少” —— 带权并查集

B 把“对立”变成“连通” —— 拓展域并查集与应用

C 状态多一维，图就多一层 —— 分层图与最短路建模

Day3 · 搜索与暴力

01

暴力骗分与搜索

今天先复盘模拟赛，再讲暴力骗分与打表，最后把 DFS 和 BFS 的进阶写法补齐。

模拟赛复盘暴力骗分与打表 DFS 与 BFS 进阶

01

PART 01 · 模拟赛复盘

先过一遍今天的四道题

一小时：每题 10~15 分钟，从关键观察讲到易错点。

演出 · 分数比大小数字 · 数位和邻居 · 子任务分层异或 · 按位独立

模拟赛复盘 · 60min

四道题，各考一件事

01

演出

不许除，交叉相乘。

02

数字

胜负看步数奇偶。

03

邻居

子任务分层拿分。

04

异或

拆到每一位再算。

复盘 · T1 · 演出

比分数别用 double

T 组询问，每组给三组节目的效果 a,b,c 和人数 x,y,z（都不超过 2×10⁹）。比较 a/x、b/y、c/z 三个分数，输出最大那组的编号，并列时输出编号小的。

1

三组各自是一个分数：效果除以人数，谁大谁上台。

2

别用 double：数字到 2×10⁹，除出来的小数已经不精确。

3

改成交叉相乘，两边都是整数，比较结果不会丢精度。

4

乘积最大到 4×10¹⁸，中间变量一定要开 long long；并列取编号小的。

read T repeat T times: read a, b, c, x, y, z A, X, ans = a, x, 1 // ① 每组是一个分数 if b*X > A*y: // ② 不用 double A, X, ans = b, y, 2 // ③ 交叉相乘 if c*X > A*z: A, X, ans = c, z, 3 // ④ 并列留小编号 print ans

复盘 · T2 · 数字

数位和游戏，只看步数奇偶

T 组询问，每组一个正整数 N（N ≤ 10⁹）。两人轮流把当前数的各位数字相加，得到的新数当作下一轮的当前数；轮到你时如果已经是一位数，算出来还是它本身，你就输了。先手赢输出 S，输输出 M。

1

先看输的条件：轮到你时是一位数，那你算出还是它，就输了。

2

所以一局只由还能做几次数位和决定，和具体是哪个数无关。

3

数步数：只要不小于 10 就把各位相加，每做一次步数加一。

4

步数是奇数先手赢，输出 S；偶数先手输，输出 M。

read T repeat T times: read n s = 0 // ① 一位数就输 while n >= 10: // ② 只看还能走几步 n = 数位和(n) // ③ 每走一步加一 s = s + 1 if s % 2 == 1: print "S" // ④ 奇数步先手赢 else: print "M"

复盘 · T3 · 邻居

两两枚举就够了

N 个人依次住在位置 1~N，每人属于一班或二班。同班两人距离 ≤ K₁、不同班距离 ≤ K₂ 就算互为邻居。输出每个人的邻居个数（2 ≤ N ≤ 3000，距离按位置之差算）。

1

先看子任务：N=2、K₁=K₂=1、全同班这三档一共 65 分。

2

N 最多 3000，两两配对不到 450 万对，O(N²) 完全够快。

3

判关系：同班看 K₁，不同班看 K₂，距离就是两人的位置之差。

4

只枚举 i < j 的对，两人各加一，不重复也不会把自己算进去。

// ① 子任务先拿：N=2、全同班这些档另有 65 分 read n, k1, k2 read s[1..n] cnt[1..n] = 0 for i = 1 .. n: // ② N 最多 3000 for j = i+1 .. n: if s[i] == s[j]: d = k1 // ③ 同班看 K1 else: d = k2 if j - i <= d: // ④ 两人各加一 cnt[i] += 1 cnt[j] += 1 print cnt[1..n]

复盘 · T4 · 异或

按位拆开，异或就能整段算

n 个数，q 次询问。每次临时把整个数组改成 a_i 与 k（op=0）或者 a_i 或 k（op=1），求区间 [l,r] 的异或和，问完恢复原数组（n, q ≤ 2×10⁵）。

1

不能每次真改数组：q 次每次 O(n)，太慢了。

2

异或按位独立，k 和 a_i 都小于 2³⁰，第 0~30 位分开算。

3

每一位开一条前缀和，就能 O(1) 数出区间里这一位有几个 1。

4

与 k 可以整段算；或 k 要逐位，k 这一位是 1 时整段全是 1。

// ① 不能每次真改数组，q 次 O(n) 太慢，先预处理 for i = 1 .. n: xr[i] = xr[i-1] ^ a[i] for b = 0 .. 30: // ② 按位独立，分位算 // ③ 每位开一条前缀和 p[i][b] = p[i-1][b] + bit(a[i],b) repeat q times: read op, k, l, r // ④ 与 k 整段算；或 k 逐位，为 1 就整段全 1 if op == 0: print (xr[r]^xr[l-1]) & k else: len = r-l+1, ans = 0 for b = 0 .. 30: if bit(k,b): ones = len else: ones = p[r][b]-p[l-1][b] if ones & 1: ans += 1 << b print ans

复盘 · 小结

复盘这四道题，记住三件事

①

先读数据范围表：每一档子任务都是一份分，稳的先拿满。

②

把状态拆开：T1 拆成分数、T2 拆成步数、T4 拆到每一位 —— 拆完基本就是模拟或前缀和。

③

算准复杂度：2×10⁵ 想 O(n log n)，2×10⁹ 记得 long long。

02

PART 02 · 暴力骗分与打表

先把能拿的分拿干净

子任务、特殊性质、打表：每一档都能换成分。

子任务驱动的打法特殊性质分打表三种形态

板块 A · 暴力骗分 · 开场

先看这道题：扑克牌

P11227 · CSP-J 2024 T1

一副牌 = 4 种花色 × 13 个点数 = 52 张。
手里已经有 n 张（可能有重复的），
问还要借几张，才能凑齐完整的一副。

数据范围说明

n ≤ 52最多就一整副

2 字符/张花色 D C H S ＋点数 A2…TJQK

!

最直接的做法

开一个 4 × 13 的表，读到一张牌就标一个。

?

这题不难，正解十几行。但它值得讲：10 个测试点里有 7 个带特殊性质。

板块 A · 暴力骗分 · 方法

分数是一档一档给的

评测怎么给分

只会写正解、没写完0 分

只写性质 A 那一档40 分

再补上性质 B 那一档70 分

全写完100 分

扑克牌的真实测试点 → 逐档翻译成一句 if

测试点特殊性质这一档怎么写

1A 两两不同52 − n，一行

2 ~ 4A 两两不同同上，还是一行

5 ~ 7B 按序给出扫一遍，和上一张比

8 ~ 10无bool[4][13] 去重

1

拿到题先翻“数据范围”表，表里每一行都是一份分。

2

每一档翻译成一句 if：这档数据长什么样，就写什么样的代码。

3

“特殊性质”栏最值钱：它直接告诉你这档数据长什么样。

4

先挑代码短、稳拿的档写；认不出的档先跳过，回头再说。

板块 A · 暴力骗分 · 写成代码

扑克牌

按刚才那张表，一档一档写下来。

1

题意换算：还差几张 = 52 减去手上“不同的牌”有几种，重复的不算。

2

去重最省事的写法：开一个 4 × 13 的布尔数组，读到就置真。

3

字符到下标：D C H S 映射成 0~3，A 2 … T J Q K 映射成 0~12。

4

最后数一数数组里有多少个真，用 52 减掉就是答案。

伪代码

seen[4][13] = false // ① 去重靠这张表 for i = 1 .. n: s = 花色编号(牌[i][0]) // ② D C H S r = 点数编号(牌[i][1]) // ③ A 2 … T J Q K seen[s][r] = true // 重复只算一次 ans = 52 - 数一数 seen 里的真 // ④ 差几张输出 ans

板块 A · 打表 · 开场

再看这道题：小木棍

P11229 · CSP-J 2024 T3

用 n 根木棍拼一个正整数，
拼出来的数不能有前导 0，
求能拼出的最小的数；拼不出来输出 −1。

每个数字要几根木棍

数字0123456789

木棍6255456376

!

最直接的做法

把所有能拼出的数枚举一遍，取最小的。

?

搜不动：要搜的是“答案”，而答案可以很长很长。
那能不能——先把答案算出来？

板块 A · 打表 · 方法

打表：先把答案算出来

小木棍是构造题，暴力搜不出来——但“答案本身”可以先跑出来。

① 硬编码表

答案很少又固定，直接抄进代码：八皇后 92 组解、卡特兰数前几项、小素数表。

② 预处理表

先算一次，之后每次 O(1) 查：筛法素数表、阶乘表、递推表。

③ 找规律

跑小数据 → 列表 → 归纳 → 写成一句不用搜的构造。

✓

打表不是作弊

它是用“计算”换“推导”：推导不出来的时候，先把答案跑出来，再回头找规律。

→

小木棍走的就是第 ③ 条：接下来两帧，一步一步把它跑成表。

?

但不是什么题都能打——什么时候该打表，下一页给判据。

板块 A · 打表 · 手推

手推：小木棍的答案表

先写暴力跑 n = 1..20，把答案抄下来。

n12345678910

ans−1174268101822

n11121314151617181920

ans20286888108188200208288688

1

位数越少越好：位数少的数一定更小，位数 = ⌈n / 7⌉。

2

位数定了，从左往右一位一位定。

3

每位从 0（首位从 1）开始试，试到“剩下的木棍还放得进剩下的位”为止。

!

归纳完一定要回头验

拿 n = 20 的答案和暴力对一遍。把巧合当规律，是打表最常见的翻车方式。

板块 A · 打表 · 判据

动手打表前，先问自己三句

?

答案范围大不大？小到能存下，就可以打。

?

询问次数多不多？多就先预处理一次，之后 O(1) 查。

?

表要占多少内存？10⁶ 个 int 是 4MB，10⁸ 个 int 是 400MB。

✓

能打：答案只依赖很小的自变量，状态能全部枚举。

✗

别打：答案规模大到存不下，或者预处理本身就要好几秒。

~

半打表：只对询问范围建表，比如区间筛、分块预处理。

!

先自检

用暴力跑几组小数据验一遍，别把巧合当规律。

板块 A · 打表 · 写成代码

小木棍

把刚才归纳出的规律，写成不用搜索的构造。

1

位数先定：位数 = ⌈n / 7⌉，位数少的数一定更小。

2

然后从左往右一位一位定，每位都从最小的数字开始试。

3

试的判据：剩下的木棍，还放得进剩下的位吗（每位要 2~7 根）。

4

所以这题不用搜：位数定下来，每位贪心取最小就行。

伪代码

if n == 1: return -1 // ① 只有 1 根拼不出来 k = 向上取整(n / 7) // ② 位数越少越好 ans = "" for pos = 1 .. k: for d = (首位从 1，其余从 0) .. 9: rest = n - 用棍数(d) if 剩余位*2 <= rest <= 剩余位*7: ans += d; n = rest; break // ③ 定下这一位 return ans // ④ 不用搜，直接构造

板块 A · 枚举 · 开场

第三道题：密码锁

P9752 · CSP-S 2023 T1

有一个 5 位的正确密码，由 5 个 0~9 的拨轮组成。
给你 n 个号码，每个都是正确密码“只转一次”的结果：
要么只转一个拨圈，要么同时转两个相邻的拨圈
（幅度相同、方向相同）。
问有多少个 5 位数可能是正确密码。

密码空间 = 5 个拨轮 × 每位 10 种

0

=

10⁵

!

最直接的做法

把所有 10⁵ 个 5 位数都试一遍。n ≤ 8，每个候选只查 n 次。

✓

所以这题不用想正解——把状态铺开，暴力就是正解。

板块 A · 枚举 · 方法

枚举之前，先估一估状态数

状态数量级 → 能不能枚举

量级怎么办

10³随便枚举，怎么写都行

10⁵能枚举，但每个状态的判定要便宜

10⁸枚举不动了，得换方法

真正的复杂度 = 状态数 × 每个状态的判定代价

状态数

10⁵

×

判定代价

10⁵

=

总复杂度

10¹⁰

超时

1

枚举的前提是状态数小：把可能的答案空间整个铺开，一个个试。

2

别只看状态数，判定代价也要算进去，两个乘起来才是复杂度。

3

“值域小”也是资源：数据种类很少时，开个桶数一数就够了。

4

枚举写起来最快、最不容易错 —— 能枚举就别硬推公式。

板块 A · 枚举 · 写成代码

密码锁

把 10⁵ 个号码铺开，逐个判定。

1

先数密码空间：一共只有 10⁵ 个号码，全部试一遍完全来得及。

2

对每个候选号码，检查它是否和每个已知号码都「只差一步」。

3

「一步」只有两种：只拨一位；相邻两位同幅同向地拨（幅度 1~9）。

4

全部满足就计数。10⁵ × n(≤8) × 5 位 ≈ 4×10⁶，很快。

伪代码

ans = 0 for s in 00000 .. 99999: // ① 候选只有 10^5 个 ok = true for i = 1 .. n: // ② 每个已知号都对上 if 不是一步(s,号[i]): ok=false; break if ok: ans += 1 // ③ 全部满足就计数输出 ans

板块 A · 枚举 · 变体

日期

P5690 · CSP-S 2019 江西

输入一个「MM-DD」形式的字符串，问最少改几位数字才能变成真实日期。题面不给年份，并规定 2 月固定 28 天。

1

合法日期正好 365 个，全都列出来逐个试，不用推公式。

2

逐月查天数表：大月 31 天、小月 30 天，题面规定 2 月固定 28 天。

3

对每个候选日期和输入的字符串逐位比较，数一数有几个数字不同。

4

所有候选里差异最小的那个就是答案。

伪代码

ans = 极大值 for m = 1 .. 12: // ① 枚举全部日期 for d = 1..天数(m): // ② 天数查表（2 月按 28） diff = 逐位比较(输入, m, d) // ③ 数几位不同 ans = min(ans, diff) // ④ 取最小改动数输出 ans

板块 A · 枚举 · 变体

直播获奖

P7072 · CSP-J 2020 T2

n 位选手依次公布成绩（0~600）。当前获奖名额 = max(1, ⌊i × w%⌋)，问每公布一人后的获奖分数线。

1

分数只有 0~600 共 601 种可能，所以不需要排序，用桶记个数就行。

2

每读入一个分数，就在对应的桶里加一。

3

要找第 k 名，就从 600 分往低处累加桶里的个数。

4

累到第 k 个，那个分数就是分数线；每轮只花 O(601)，很快。

伪代码

cnt[0..600] = 0 // ① 值域只有 601 种 for i = 1 .. n: 读入 score cnt[score] += 1 // ② 桶里记个数 k = max(1, i * w / 100) // ③ 当前获奖名额 s = 0 for v = 600 .. 0: s += cnt[v] if s >= k: break // ④ 第 k 个就是分数线输出 v

03

PART 03 · DFS 进阶

搜得完，也要剪得掉

同一套递归框架，靠剪枝、加深和折半撑住指数级的规模。

剪枝三件套迭代加深折半搜索记忆化搜索

板块 B · DFS 进阶 · 开场

先看这道题：社团招新

P14361 · CSP-S 2025 T1

n 个人（n 是偶数），每人给 3 个部门的满意度。
分完要求：任何一个部门的人数都不超过 n/2。
求满意度总和的最大值。

数据范围：n ≤ 10⁵，满意度 ≤ 2×10⁴

每个人 3 种选法，n 个人一起分

每人

3 种

×

n 个人

n

=

方案数

3ⁿ

3ⁿ 在不同数据下

数据暴力枚举 3ⁿ

n ≤ 103¹⁰ = 59049，稳稳过

n = 10⁵3ⁿ 想都别想

!

最直接的做法

每个人有 3 种选法，3ⁿ 枚举所有分配方案。

?

卡点：n 到 10⁵ 时 3ⁿ 想都别想 —— 暴力只能拿小分。

板块 B · DFS 进阶 · 方法

暴力不只是拿小分，还是你的尺子

社团招新：暴力先拿 20 分，但它的用处不止这些

① 拿小分

→

② 当尺子

→

③ 找冗余

三样各是什么

用处怎么做

拿小分n ≤ 10 的那一档，直接交 3ⁿ 枚举

当尺子正解写完，和暴力对拍，心里才有底

找冗余盯着暴力问：哪一步其实不用做？

这题的第 ③ 步3ⁿ 会爆炸 —— 但不用真去枚举：先各取最满意的部门，超了再调

1

先写最笨的：能过小数据就行，别一上来就想着推正解。

2

暴力写完别删：对拍的时候，它比任何调试手段都好用。

3

盯着暴力问自己：这个循环真的每一次都必须跑吗？

4

大多数“优化”不是换算法，而是发现某一步是多余的。

板块 B · 先暴力再优化 · 写成代码

社团招新

回到社团招新：先各取最优，超了再调回来。

1

先写暴力：n ≤ 10 时 3ⁿ 枚举所有分法，能拿小分，还能留着对拍。

2

先不管限制：每个人各取自己最满意的部门，得到的是答案的上界。

3

关键观察：超员的部门最多只有一个，因为两个都超过 n/2 就超过 n 了。

4

修回去：把超出的那些人里“换部门损失”最小的挪走，取损失最小的几个。

伪代码

sum = 0 for i = 1 .. n: // ① 每人先取最大 best = max(a[i][1], a[i][2], a[i][3]) cnt[最大部门的编号] += 1 sum += best if 所有 cnt[j] <= n/2: 输出 sum // ② 没超就直接结束 // ③ 只在“最满意部门就是 j”的人里算损失 loss[i] = a[i][j] - max(另外两个) sort(loss)，取前 cnt[j] - n/2 个输出 sum - 这些 loss 的和 // ④ 修完就是答案

板块 B · 剪枝 · 开场

再看这道题：考前临时抱佛脚

P2392 · 洛谷经典

4 科作业，第 i 科有 sᵢ 道题、每题耗时 aᵢ。
左右脑能同时做同一科的两道题，一科一科来。
求把全部作业做完的最短时间。

四科互不影响，答案 = 四科各自最短时间相加

第 1 科

s₁

第 2 科

s₂

第 3 科

s₃

第 4 科

s₄

=

答案

Σtᵢ

单科：每题给左手还是右手

数据说明

sᵢ ≤ 20单科 2²⁰ ≈ 10⁶ 种分法，暴力能过

耗时 ≤ 60分给左右手，取较慢的那只手

!

最直接的做法

每题枚举给左手还是右手，2ˢ 种；s ≤ 20 → 2²⁰ ≈ 10⁶。

?

卡点：单科就是一道搜索题 —— 让较慢的那只手尽量小。

板块 B · 剪枝 · 方法

剪枝：进函数先问一句“还有必要走吗”

2 的幂：大一点点就没了

规模量级结果

2²⁰≈ 10⁶这一题够用

2³⁰≈ 10⁹换组数据就超时

2⁴⁰≈ 10¹²想都别想

!

而 2²⁰ 里绝大多数分支，一眼就知道不行

进函数先判断“这条路还有必要往下走吗”；答“没必要”就 return —— 整棵子树都不用展开。

1

可行性剪枝：当前状态已经不可能凑出合法解，直接回头。

2

最优性剪枝：当前代价已经赢不了已知答案，直接回头。

3

搜索顺序：把更可能出好解的分支排前面，让上界尽快变紧。

4

越靠上剪越值钱：砍掉的是一整棵子树，不是一条路径。

板块 B · 剪枝 · 手推

手推：就用这一科走一遍

一科 4 道题，耗时 9 7 5 3，总和 24，下界 ⌈24/2⌉ = 12；先做耗时的题，目标 min max(左手, 右手)。

第 1 题第 2 题第 3 题第 4 题LR沿途 (L, R)结论

左9左7左5左32409,0 → 16,0 → 21,0 → 24,0best = 24

左9左7左5右32139,0 → 16,0 → 21,0 → 21,3best = 21

左9左7右5左31959,0 → 16,0 → 16,5 → 19,5best = 19

左9左7右5右31689,0 → 16,0 → 16,5 → 16,8best = 16

左9右7左5左31779,0 → 9,7 → 14,7 → 17,7max 17 ≥ 16　✂ 最优性

左9右7左5右314109,0 → 9,7 → 14,7 → 14,10best = 14

左9右7右5左312129,0 → 9,7 → 9,12 → 12,12best = 12 = 下界 → 最优

左9右7右5右39159,0 → 9,7 → 9,12 → 9,15max 15 ≥ 12　✂

右9左7左5—1290,9 → 7,9 → 12,9max 12 ≥ 12　✂

右9左7右5—7140,9 → 7,9 → 7,14max 14 ≥ 12　✂

右9右7——0160,9 → 0,16max 16 ≥ 12　✂

1

best 一路从 24 缩到 12：先做耗时的题，好解来得早。

2

摸到 L=12、R=12 就是下界 12，不可能更好 —— 剩下的分支全可以剪掉。

3

剩下 5 处全是 max ≥ best 剪掉的，整棵子树都没展开。

!

节点数：31 → 21

不剪枝 31 个 → 剪完 21 个；剪枝剪的是搜索量，答案一个字都不变。

板块 B · 剪枝 · 写成代码

把三把剪刀写进去

1

四科各做一次搜索，答案相加；每科独立，互不影响。

2

剪刀写在进函数的第一行：max(L, R) ≥ best 就回头。

3

先做耗时的题：best 早点变小，后面才剪得动。

4

易错：条件写太松等于没剪；写太紧会把正解剪掉，写完用暴力对拍。

伪代码

// 四科各做一次，答案相加 best = 无穷大 // 初值必须是无穷大 dfs(i, L, R): if max(L, R) >= best: return // ① 最优性剪枝 if i > s: best = max(L, R); return dfs(i + 1, L + a[i], R) // ② 这道给左手 dfs(i + 1, L, R + a[i]) // ③ 这道给右手 sort(a, 从大到小) // ④ 先做耗时的输出四科的 best 之和

板块 B · 迭代加深 · 方法

最少步数问题：BFS 存不下，DFS 走不到

场景：每层 8 种走法，答案可能在第 10 层

做法会发生什么

BFS第 d 层要存 8^d 个状态：8¹⁰ ≈ 10⁹ → 队列直接爆内存

DFS一条道走到黑，答案在第 2 层也可能找不到

迭代加深：深度上限从 0 开始，一层一层放宽

lim = 0

→

lim = 1

→

lim = 2

→

…

每次只搜深度 ≤ lim 的；第一个搜到的 lim，就是最短深度。

1

什么时候用：答案深度浅、每层分支多、状态存不下（BFS 会 MLE）。

2

代价有限：总量约是单次最深那轮的 b/(b−1) 倍 —— b=8 时只多 14%。

3

加个估价：已走深度 + h(状态) > lim 就剪，这就是 IDA*。

4

什么时候别用：答案深度可能很深（比如要走 20 层）。

板块 B · DFS 进阶 · 手推

手推：lim = 0、1、2 各搜了什么

接着上面的场景：每层 2 个分支的搜索树，答案在深度 2。

lim搜哪些层碰到几个节点累计

0只搜第 0 层11

1重搜第 0 ~ 1 层1 + 2 = 34

2重搜第 0 ~ 2 层1 + 2 + 4 = 7，找到11

合计重复搜的浅层 1 + 3 = 4一共碰了 1 + 3 + 7 = 11 个—

1

重复搜的浅层不是零头：总量约是单次最深那轮的 b/(b−1) 倍。

2

分支数越大、答案深度越小，迭代加深就越划算。

3

真正的收益是内存：队列里永远只有“当前这一层”的量级 —— b=2 时时间翻倍，b=8 时才多 14%。

!

换来的不是时间，是空间

对比 BFS：队列还要同时存下“当前这一层”（第 2 层是 4 个）再加 visited 去重表，1+2+4 = 7 个都得留着；一路 DFS 则可能扎进深度 5 的死胡同。

板块 B · 折半搜索 · 方法

2⁴⁰ 枚举不完，就拆成两个 2²⁰

场景：N 场比赛各有票价，预算 M，问几种观赛方案（N ≤ 40）

每场选或不选

2⁴⁰

→

前半

2²⁰

+

后半

2²⁰

2⁴⁰ ≈ 1.1 × 10¹² 枚举不完；2²⁰ ≈ 1.0 × 10⁶，拆成两半就都能枚举。

套路：前半存表，后半到表里配对

①sa = 枚举前半的所有取值　// 2^(n/2)

②sb = 枚举后半的所有取值，sort(sb)　// 排序或塞哈希表

③for x in sa: 数一数 sb 里 ≤ M − x 的有几个，累加

1

用在哪：n 到 40 左右，直接枚举 2ⁿ 超时，但 2²⁰ ≈ 10⁶ 跑得动。

2

套路：前半枚举的结果存起来，后半枚举时去表里配对。

3

配对靠排序：二分、双指针、哈希都行，多出来的只是排序时间。

4

前提：答案要能由两半拼起来，目标函数对两半是可合并的。

板块 B · DFS 进阶 · 手推

手推：两半怎么拼起来

接着上一帧那道题：4 场比赛，票价 3 5 7 11，预算 16，问几种观赛方案。

前半 {3, 5} 子集和 0 3 5 8　·　后半 {7, 11} 子集和 0 7 11 18，排好序 sb = [0, 7, 11, 18]

前半 x还能花 16 − xsb 里 ≤ 它的方案数

0160, 7, 113 种

3130, 7, 113 种

5110, 7, 113 种

880, 72 种

合计—3 + 3 + 3 + 211 种

1

前半的每种取法，都去后半的表里“找一个搭档”，配上就是一组方案。

2

表排好序，配对就变成二分：找“最大的不超过 S − x”，再数个数。

3

4 个数看着简单，换成 40 个照样跑得动：前半 2²⁰ 张表，后半 2²⁰ 次二分。

!

11 种里含“一场都不看”

这就是“枚举不完就分两半”的完整流程，套路固定，背下来就能用。

板块 B · 记忆化 · 开场

最后一道题：Function

P1464 · 洛谷经典

// 递归函数 w(a,b,c) 按四条规则往下递归 ① 有一个 ≤ 0 → 1 ② 有一个 > 20 → w(20, 20, 20) ③ a < b 且 b < c → w(a,b,c-1) + w(a,b-1,c-1) − w(a,b-1,c) ④ 其它 → w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) − w(a-1,b-1,c-1)

多组询问，T ≤ 10⁵，求 w(a,b,c)。

题面给的两条信息

信息意味着什么

T ≤ 10⁵多组询问，一组一组算肯定来不及

a = b = c = 15题面自己就写了：“调用的次数将非常的多”

!

最直接的做法

照着四条规则，把递归函数原样写出来。

?

卡点：直接递归会爆炸 —— 下一帧我们数一数到底炸成什么样。

板块 B · 记忆化 · 方法

记忆化：同一个子问题，别算第二遍

记忆化只做两件事

memo[状态]怎么办

算过直接 return

没算过算完存进 memo 再 return

状态就是参数：a、b、c 都被折进 0~20

a

21

×

b

21

×

c

21

=

状态数

9261

!

递归里最浪费的事：同一组参数反复算

w(15,15,15) 会反复用到 w(0,1,2)：光是这一个状态就被调用了 8.7 × 10¹² 次。

1

状态就是参数：把 (a,b,c) 拼成一个下标，同一个下标就是一个子问题。

2

这题的状态数很小：a、b、c 都被折进 0~20，一共 21³ = 9261 个。

3

转移就是递归式，边界就是终止条件 —— 记忆化和 DP 是同一件事。

4

判断能不能记忆化：同一个状态，答案是不是永远一样。

板块 B · 记忆化 · 手推

手推：直接递归到底炸成什么样

数一数朴素递归 w(15,15,15) 到底调用多少次。

量数量级说明

有效状态（0~20 这 21 个取值）21³ = 9261不同的 (a,b,c) 一共这么多

朴素递归总调用次数≈ 7.4 × 10¹³ 次题面那句“调用的次数将非常的多”

其中 w(0,1,2) 被调用8.7 × 10¹² 次边界状态，每次立刻返回

其中 w(1,1,3) 被调用3.9 × 10¹² 次非边界，每次要展开 5 个节点的子树

加了记忆化：真正进函数体的次数≤ 9261每个状态只算一次

差了多少7.4 × 10¹³ → 9261差了约 80 亿倍

1

浪费在哪：w(0,1,2) 被调用 8.7 万亿次，w(1,1,3) 被调用 3.9 万亿次。

2

非边界状态每次都要整棵重新展开：w(1,1,3) 的子树有 5 个节点。

3

状态数只有 9261，收益是指数级的；成本几乎为零（一个 21³ 的数组）。

!

这就是记忆化的判据

状态数远小于递归树的节点数，就该上记忆化。

板块 B · 记忆化 · 写成代码

Function

回到 Function：把 memo 表加进递归里。

1

先看规则：a、b、c 一超过 20 就被折回 w(20,20,20)。

2

所以有效状态只有 0~20 这 21 个取值，一共 21³ = 9261 个。

3

开一个 memo[21][21][21]，算过就直接返回，没算过才算一遍。

4

剩下是细节：≤ 0 要先判（题面说按最上面的规则），-1 -1 -1 结束。

伪代码

// ① 有效状态只有 0..20，开个 21³ 的表 w(a, b, c): if a <= 0 或 b <= 0 或 c <= 0: return 1 if a > 20 或 b > 20 或 c > 20: return w(20, 20, 20) if 算过(a,b,c): return memo[a][b][c] // ② 查表 if a < b 且 b < c: ans = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) else: ans = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1) memo[a][b][c] = ans // ③ 存起来 return ans

04

PART 04 · BFS 进阶

队列一开，最短路自己长出来

网格、多源、状态、双向：同一个队列，四种花样。

网格 BFS 模板多源 BFS 状态 BFS 双向 BFS

板块 C · BFS 进阶

网格上两点，最少走几步

场景：n × m 网格，有些格子是障碍，从起点走到终点，求最少步数

最直接深搜所有路线取最短 —— 路线是指数级的多，搜不完

BFS 的队列有一个不变量

0

→

1

→

2

→

…

出队顺序：距离 0, 0, 1, 1, 1, 2, 2, …
队列里任意两个元素，距离最多差 1

!

于是

第一次访问到某个格子，走的就是最短步数。如果还有更短的路，它应该更早被访问到才对。

1

一层一层往外扩：处理完所有距离 d 的点，才会碰距离 d+1 的点。

2

所以每个格子只写一次 dis，总时间就是 O(格子数)，不用再更新。

3

这个性质要求每条边代价相同；边权变成 0/1，队列的单调性就没了。

4

对比记忆：Dijkstra 是“当前最近的优先”，BFS 就是它的无权版本。

板块 C · BFS 进阶 · 手推

手推：3×3 网格上的一圈一圈

接着上面的场景：3×3 网格，(2,2) 是障碍，从 (1,1) 出发。

队列的变化：每一轮出队一个点

轮次出队新写入的 dis出队后的队列

初始——(1,1)

第 1 轮(1,1)(1,2)=1、(2,1)=1(1,2) (2,1)

第 2 轮(1,2) (2,1)(1,3)=2、(3,1)=2(1,3) (3,1)

第 3 轮(1,3) (3,1)(2,3)=3、(3,2)=3(2,3) (3,2)

第 4 轮(2,3) (3,2)(3,3)=4(3,3)

0

1

2

1

#

3

2

3

4

网格（# 是障碍
从左上角 (1,1) 出发）
格子里写下的 dis 表
颜色 = 第几圈写的

第 0 圈 (1,1)

→

第 1 圈 (1,2) (2,1)

→

第 2 圈 (1,3) (3,1)

→

第 3 圈 (2,3) (3,2)

→

第 4 圈 (3,3)

1

注意 (2,2) 是障碍，但 (1,3) 还是能从 (1,2) 绕过去，距离 2。

2

队列里永远是同一层或相邻层的点，不会出现距离差 2 的情况。

!

没 visited 会退化

每个格子只被写一次，所以总时间是 O(格子数)，不是 O(格子数²)；要是没有 visited，同一个格子会被反复入队，直接退化成指数级。

板块 C · 网格 BFS · 写法

网格 BFS 模板（背下来）

四个零件装上去，网格题就有一套固定写法。

1

方向数组：dx = {0,1,0,-1}、dy = {1,0,-1,0}，别手写四段 if。

2

两条 continue：一条挡越界和障碍，一条挡“已经访问过”。

3

dis 数组顺便当 visited 用，不用另开一个 bool 数组。

4

多组数据记得每次清空 dis —— 这是“样例过了却全 WA”的头号原因。

伪代码

dis[][] = -1; dis[sx][sy] = 0 // ① 起点距离 0 q.push({sx, sy}) while q 非空: (x, y) = q.front(); q.pop() for d = 0 .. 3: // ② 方向数组，四个方向挨个试 (nx, ny) = (x + dx[d], y + dy[d]) if 越界或是障碍: continue if dis[nx][ny] != -1: continue dis[nx][ny] = dis[x][y] + 1 // ③ 层数即距离 q.push({nx, ny}) // ④ 等下一层再扩

板块 C · BFS 进阶 · 当堂写热身

地图探险

P11228 · CSP-J 2024 T2

机器人站在网格上，每步要么往前走一格，要么原地右转；走完 k 步，问它经过了多少个不同的格子（含起点）。

1

先说清楚：这题正解是纯模拟，不是 BFS —— 路线只有一条，照着规则走就行。

2

但它练的是网格题的基本功：方向写成数组，边界写成一句判断。

3

状态就是 (位置 x, y, 朝向 d)：先算下一步坐标，再判越界和障碍。

4

k ≤ 10⁶，一步一步走就是 O(k)；开个标记数组统计格子，别忘了先把起点标上。

伪代码

dx[4] = {0, 1, 0, -1} // ① 0 东 1 南 dy[4] = {1, 0, -1, 0} // 2 西 3 北 vis[x][y] = true // ② 起点也算走过 for step = 1 .. k: nx = x + dx[d]; ny = y + dy[d] if 越界或地图[nx][ny] == 'x': d = (d + 1) % 4 // ③ 走不了就右转 else: x = nx; y = ny // ④ 能走就走过去 vis[x][y] = true // ⑤ 每步都标上输出 vis 里真值的个数

板块 C · BFS 进阶

多源 BFS：所有起点一起入队

场景：草地有 3 个起火点，火每步烧到相邻格子

求什么每个格子最快多久被烧到 —— 也就是到“最近火源”的距离

最直接对每个火源各跑一次 BFS，再取最小

对每个火源各跑一次，复杂度就是 O(格子数 × 火源数)

格子数

N

×

火源数

3

=

总复杂度

O(N × 3)

白慢好几倍

多源 BFS：所有起点一起入队

dis[][] = -1

→

所有起点 dis = 0

→

一起入队，都是第 0 层

→

while q 非空: …

→

其余一个字都不用改

1

求什么：每个点到“最近的起点”的距离，比如多个出口、多个火源。

2

怎么写：所有起点距离置 0 后一次性入队，剩下的代码一个字都不用改。

3

为什么对：相当于虚拟一个超级源点连向所有起点，最短路性质不变。

4

反过来也常用：从所有终点倒着搜，一次算出每个点到最近终点的距离。

板块 C · BFS 进阶 · 手推

手推：两个火源，谁先烧到

接着起火那道题：一排 5 个格子，火源在 1 号和 5 号。

格子编号

1

2

3

4

5

初始

0

·

0

第 1 轮

0

1

·

1

0

第 2 轮

0

1

2

1

0

粉色 = 两个火源　黄色 = 第 1 轮写的　绿色 = 第 2 轮写的

轮次出队做了什么dis

第 0 轮—起点 1 号、5 号一起入队0 · · · 0

第 1 轮1、5写 2 号 = 1；写 4 号 = 10 1 · 1 0

第 2 轮2、4写 3 号 = 2；4 出队时 3 号已有值，跳过0 1 2 1 0

1

两个起点在同一层，一起往外扩，谁先碰到就是谁离得更近。

2

3 号先被 2 号写了 2，4 号再来就被“访问过”挡掉，不会重复写。

3

所以多源 BFS 的复杂度还是 O(格子数)，和单源一样，只是起点多了几个。

!

一遍就够

分两次单源 BFS：5 个格子要跑 2 遍；多源 BFS：一遍就够，每个格子只写一次。
如果对每个起点各跑一次 BFS，就是 O(格子数 × 起点数)，白慢好几倍。

板块 C · 状态 BFS · 开场

最后一道题：加工零件

P5663 · CSP-J 2019 T4

n 个工人，之间有双向传送带。
x 号要生产第 L 阶段的零件 → 与 x 相连的工人都要生产第 L−1 阶段；
要生产第 1 阶段 → 邻居要提供原材料。
工单问：a 号要生产第 L 阶段，1 号要不要提供原材料？

一条传送带上的连锁反应

a 要生产第 L 阶段

→

与 a 相连的工人生产 L−1

→

…

生产第 1 阶段

→

邻居要提供原材料

规模范围

n, m, q≤ 10⁵

L≤ 10⁹

!

最直接的做法

照着题意一层一层往下递归，看 1 号有没有被点到。

?

L 可以到 10⁹，递归层数直接爆炸，一层都跑不完。
卡点：要找一个和 L 有关、但不用真的递归 L 层的判据。

板块 C · 状态 BFS · 方法

状态 BFS：把“局面”变成一个点

图上的点不一定是格子，也可以是“局面”

图上的点点代表什么

普通 BFS坐标 (x, y)

状态 BFS局面（棋盘、水量、密码、步数奇偶…）

关键：把局面编码成一个能查重的值

状压

用一个整数的每一位表示一个开关

进制

多位数拼成一个整数

字符串

局面复杂时，直接存字符串

!

加工零件要的就是这个：把“步数奇偶”也当成状态的一维。

1

什么时候用：走一步就换一个局面，比如棋盘、水壶、密码转盘。

2

编码要求：能唯一对应一个局面，而且能快速比较、快速查重。

3

查重怎么存：编码范围小就开数组，范围大就上哈希表或 map。

4

最常见的坑：状态设计少了一维，把两个不同局面当成同一个。

板块 C · BFS 进阶 · 手推

手推：状态少一维，答案就错

接着加工零件：两种状态设计，看哪一种能回答问题。

图

1

—

2

—

3

问 (a, L)：1 号要不要提供原材料

状态设计从 1 号出发算出来的距离问 (2, 2)结果

设计一

状态 = (工人)

d[u] = 从 1 到 u 的最短长度

d[1]=0　d[2]=1　d[3]=2 d[2] = 1 ≤ 2 → 判 Yes ✗ 错

实际答案是 No —— 从 2 到 1 没有长度恰好 2 的通路

设计二

状态 = (工人, 步数奇偶)

偶数步走不到 2 号

d[1][0]=0　d[1][1]=∞
d[2][1]=1　d[2][0]=∞
d[3][0]=2　d[3][1]=∞ L 是偶数 → 查 d[2][0] = ∞ → No ✓
问 (3, 2)：查 d[3][0] = 2 ≤ 2 → Yes ✓ ✓ 对

1

状态少一维，能表达的信息就少一截：只知道最短，不知道“恰好”。

2

加上“步数奇偶”这一维，状态数翻倍，但问题就能回答了。

4

这一招就是“分层图”的雏形：多一个维度，就在图上多复制一层。

!

判断状态够不够的标准

问题问到的每一个区分，状态里都要有。

板块 C · 状态 BFS · 写成代码

加工零件

回到加工零件：状态扩成 (工人, 步数奇偶)。

1

先推小情况：L=1 时 1 号要提供 ⟺ 1 和 a 相邻；L=2 时要存在 a-b-1 两步的路。

2

一般化：1 号要提供 ⟺ 存在一条从 a 到 1、长度恰好是 L 的通路。

3

长度恰好难搜，但多走两步来回走一条边就能补上（前提是 1 号有边），所以只看最短路和奇偶。

4

把状态扩成 (工人, 步数奇偶)，从 1 号 BFS；查询就查 d[a][L 的奇偶] ≤ L。

伪代码

d[1..n][0..1] = 无穷大 // ① 二维距离数组 d[1][0] = 0; q.push({1, 0}) while q 非空: (u, p) = q.front(); q.pop() for v in 邻居(u): // ② 一层一层扩 if d[v][p ^ 1] 还没算过: d[v][p ^ 1] = d[u][p] + 1 q.push({v, p ^ 1}) // ③ 奇偶翻转一位查询 (a, L): // ④ 回答询问 if 1 号没有传送带: 输出 No // ⑤ 孤立点特判 if d[a][L & 1] <= L: 输出 Yes else: 输出 No

板块 C · 双向 BFS

双向 BFS：两头一起搜，中间碰头

场景：状态数随层数指数级涨，每层 8 种走法、答案在第 10 层

做法要扩多大

单向 BFS扩到第 5 层就 8⁵ ≈ 3 万，第 10 层是 10⁹ → 存不下

双向 BFS两边各扩 5 层，各 3 万，合起来才 6 万

宽度对照

单向：扩到深度 d

b^d

→

双向：两边各扩 d/2

2 · b^(d/2)

写法：起点和终点各开一个队列

visS[起点]=1　visT[终点]=2

→

两个方向各做标记

while 两个队列都非空

→

挑元素少的那一边，扩一层（谁小扩谁）

新扩出的点若被另一边访问过 → 碰头，两边距离相加

1

用在哪：状态数随层数指数级涨，单向 BFS 扩到一半就爆内存/时间。

2

省在哪：两边各扩一半深度，宽度从 bᵈ 掉到大约 2b^(d/2)。

3

细节：每次扩“当前更小”的那一边；碰头判定要查另一边的标记。

4

往前看：边权变成 0/1 就换双端队列（0-1 BFS，明天讲）；带估价的是 A*。

板块 C · BFS 进阶 · 手推

手推：两头扩，省在哪里

接着上面的场景：每个状态 2 个后继、2 个前驱的状态图，起点第 0 层、终点第 4 层。

S

T

绿色 = 从起点 S 往下扩 2 层　粉色 = 从终点 T 往上扩 2 层　黄色 = 第 2 层在中间碰头

做法碰到的节点合计

单向 BFS一层一层扩到第 4 层：1 + 2 + 4 + 8 + 1631 个

双向 BFS两边各扩 2 层，在中间碰头：起点侧往下扩 1 + 2 + 4 = 7；终点侧往上扩 1 + 2 + 4 = 714 个，比 31 少一半还多

层数越多差距越大b=2、d=20 时：单向约 2²¹−1 ≈ 210 万个节点，双向约 4 千—

1

两边各扩一半深度，宽度就从 bᵈ 掉到大约 2b^(d/2)。

2

每次挑“当前更小”的那一边扩，收敛最快；这里两边一样大，轮流来。

!

能这么干的前提

从终点往回走，和从起点往前走，规则是一样的。如果图是有向的、反向不好走，那就老老实实单向 BFS。
代价：要维护两个队列、两份标记，还要判碰头。

Day3 · 收尾

今天走完了五件事

① 复盘模拟赛四题：演出、数字、邻居、异或。
② 暴力骗分：按数据范围表分档下手，特殊性质单独写。
③ 打表：硬编码、预处理、找规律，写完先用暴力自检。
④ DFS 进阶：剪枝三件套、迭代加深、折半搜索、记忆化。
⑤ BFS 进阶：网格模板、多源、状态编码、双向。

下节课

Day4 · 图论与树论（上）：0-1 BFS 与分层图、Floyd 的三个视角、建图建模。

⚑

回去把今天的例题正解各打一遍。

Day4 · 图论与树论（上）

02

图论与最短路

今天先复盘模拟赛的四道题，再讲三块：0-1 BFS、Floyd 的三个视角、反图与最短路计数。

模拟赛复盘 0-1 BFS Floyd 的三个视角反图与最短路计数

01

PART 01 · 模拟赛复盘

四道题，各考一件事

→

每题留两分钟对拍

①

开考先花三分钟把四道题扫一遍，标出“读完就知道怎么写”的那道，先写掉。

②

卡住的题别死磕：顺着数据范围表把能拿的子任务分先写进去，白拿的分先落袋。

③

每题写完留两分钟对拍小样例 —— 顺序、去重、边界这些坑，小数据都能撞出来。

复盘 · 小结

四题共性：把问题翻译成图、扫描、分解、区间

① 图

路线问“最少几条边”，翻译成无权图最短路 —— BFS 一层层扩就对。

无权图 BFS

② 扫描

纸带先内层取 max、再外层取 min；顺序写反，整题就废。

内层 max 外层 min

③ 分解与区间

对称差拆成质因子集合的对称差；消消乐把顺序问题变成区间 DP。

质因子集合区间 DP

02

PART 02 · 0-1 BFS

边权只剩两种值的时候

同类走一步 0 元、异类 1 元 —— 队列得两头都能进。

双端队列 0-1 BFS 队列里的距离差 ≤ 1 什么时候换 Dijkstra

板块 A · 0-1 BFS · 开场

先看这道题：小明的游戏

P4554 · 洛谷经典

n × m 的棋盘，每格只可能是 # 或 @。
小明从起点 (x₁, y₁) 出发，
每步向上、下、左、右走一格。
走进同类型的格子花 0，
走进不同类型的格子花 1。
问走到终点 (x₂, y₂) 最少花多少。
多组数据，读到 n = m = 0 结束。

数据范围

1 ≤ n, m ≤ 1020% 的数据

1 ≤ n, m ≤ 30040% 的数据

1 ≤ n, m ≤ 500100% 的数据

!

最直接的做法

从起点跑一遍 BFS，第一次走到终点就输出步数。

?

卡在哪：这题的花费不是步数 —— 绕远路反而可能更便宜，“第一次到 = 最近”当场失效。

板块 A · 0-1 BFS · 方法

边权有了 0，普通 BFS 就失灵

图：起点 1，3 个点 3 条边，权只有 0 和 1

1

—1→

2

原来就有的边

1

—0→

3

再补一条权 0 的边

2

—0→

3

高亮 = 权 0

同一条 1 → 3，两种算法两种答案

算法怎么算 d[3]结果

普通 BFS按边数：1 直接连到 31

0-1 BFS1→3 不花代价0

d[2] = 1，d[3] = 0 —— 差就差在这

1

普通 BFS 靠一条性质：队列里的距离单调不减，先出队的一定最近。

2

这条性质来自“每走一条边距离 +1”；边权出现 0 之后，走一步可能不花代价。

3

于是“第一次到 = 最近”崩了：按边数排出来的层数，不再是距离。

4

修法很朴素：0 边插到队首、1 边排到队尾 —— 队列换成一个双端队列。

板块 A · 0-1 BFS · 方法

0 边插队首，1 边排队尾

伪代码 · 双端队列版 BFS

deque = {起点}; dis[起点] = 0 while deque 非空: u = deque.pop_front() // ① 每次取队首 for v, w in 边(u): // ② 更小才松弛 if dis[v] > dis[u] + w: dis[v] = dis[u] + w if w == 0: deque.push_front(v) // ③ 0 边插队首 else: deque.push_back(v) // ④ 1 边排队尾

①

0-1 BFS = 普通 BFS 加一条规矩：代价 0 的边走队首，代价 1 的走队尾。

②

松弛还是那句话：dis[v] > dis[u] + w 才更新，w 就是这条边的权。

③

为什么插队首：0 边不涨距离，新点必须排在“同一距离”那批的最前面。

④

全是 1 时永远排队尾，就退化成普通 BFS —— 所以它是 BFS 的推广。

板块 A · 0-1 BFS · 手推

手推：绕远路，反而一分不花

3 × 3 的棋盘，起点 (0, 0)、终点 (0, 2)；每一步都记下队列长什么样。

步出队（距离）队列（队首 → 队尾）这一步发生了什么

0—[(0,0)]起点距离 0

1(0,0) d=0[(1,0), (0,1)](1,0) 同类 → d=0 插队首；(0,1) 异类 → d=1 排队尾

2(1,0) d=0[(2,0), (0,1), (1,1)](2,0) 同类 → d=0 插队首；(1,1) 异类 → d=1 排队尾

3(2,0) d=0[(2,1), (0,1), (1,1)](2,1) 同类 → d=0，插队首

4(2,1) d=0[(2,2), (0,1), (1,1)](2,2) 同类 → d=0，插队首

5(2,2) d=0[(1,2), (0,1), (1,1)](1,2) 同类 → d=0，插队首

6(1,2) d=0[(0,2), (0,1), (1,1)](0,2) 同类 → d=0，插队首

7(0,2) d=0[(0,1), (1,1)]终点出队，答案 0

1

棋盘 @#@ / @#@ / @@@：中间一列是 #，外圈是 @。

2

队列里只有 d 和 d+1 两种距离，单调性保住了。

3

出队顺序一路绕外圈，(0,2) 出队时距离还是 0。

!

两个“最短”不是一回事

按步数最短：(0,0)→(0,1)→(0,2)，2 步就到，可路上跨了两个 #，花费 2。
按花费最短：绕外圈走 6 步，花费 0。
坐标是 0 起的，读入别减一。

板块 A · 0-1 BFS · 方法

队列里的距离差，不会超过 1

某一步的队列（队首 → 队尾）

队首 · 点 5

d = 1

→

点 6 · 队尾

d = 2

非降，
最大最小差 = 1

新元素插进去，距离是多少

插入方式新元素的距离

0 边插队首新值 = 当前最小值

1 边排队尾新值 = 当前最小值 + 1

1

不变量：队列里任意两个元素的距离差 ≤ 1，队首一定是最小的那个。

2

0 边贴着队首插入、1 边贴着队尾插入，两端各自只差 1，中间自然更不会超。

3

所以出队顺序天然按距离非降 —— 这正是 Dijkstra 用优先队列保证的事。

4

复杂度 O(V+E)：每个点最多进队两次，出队时 d > dis[u] 的旧副本直接跳过。

板块 A · 0-1 BFS · 判据

边权是几，就用哪把刀

?

边权全是 1 ？—— 普通 BFS 就够，队列都不用换。

?

边权只有 0 和 1 ？—— 双端队列：0 边插队首、1 边排队尾。

?

边权是 ≤ K 的小整数？—— 开 K+1 个桶，按距离分桶。

?

边权任意？—— 只能上堆优化的 Dijkstra。

✓

两种边权 · 0 和 1：双端队列。
小明的游戏、电路维修都是这一档。

~

小整数边权 · ≤ K：开 K+1 个桶。

✗

任意边权：堆优化 Dijkstra。

!

一句话：双端队列 = 两个桶

0-1 BFS 就是桶排序版 Dijkstra：桶只有两个（距离 d 和 d+1），双端队列正好当这两个桶用。

板块 A · 0-1 BFS · 写成代码

小明的游戏

回到小明的游戏：把 BFS 的队列换成双端队列，其余一个字不改。

1

边权只有 0 和 1：同类插队首、异类排队尾。队列里始终只有 d 和 d+1 两种距离。

2

松弛还是那句 dis[v] > dis[u] + w；这里的 w 就是“落脚格和当前格类型不同”。

3

同一个点可能被塞进队列好几次；出队时发现 d > dis[x][y] 就是旧副本，直接跳过。

4

多组数据：读到 n = m = 0 结束；坐标从 0 开始，答案是 dis[x₂][y₂]。

伪代码 · 双端队列 BFS

读 n, m while n != 0 or m != 0: // ⑤ 多组数据读 n 行棋盘; 读 x1 y1 x2 y2 dis[0..n-1][0..m-1] = ∞ dis[x1][y1] = 0; dq = {(x1,y1)} while dq 非空: (x, y, d) = dq.pop_front() // ① 取队首 if d > dis[x][y]: continue // ② 旧副本 for 四个方向 (dx, dy): nx = x+dx; ny = y+dy if 越界: continue w = (a[nx][ny] != a[x][y]) // ③ 同类 0 异类 1 if dis[x][y] + w < dis[nx][ny]: dis[nx][ny] = dis[x][y] + w if w == 0: dq.push_front((nx,ny)) else: dq.push_back((nx,ny)) // ④ 输出 dis[x2][y2] 读 n, m

板块 A · 0-1 BFS · 变体

电路维修

P4667 · BalticOI 2011

N × M 的电路板，每格一条对角导线；电源在左上、灯在右下，元件可转 90°，问最少转几个才能点亮。N, M ≤ 500，时限只有 150 ms。

格子里是权 0 的边（顺导线，不用转）权 1 的边（转 90° 才通）

\(i,j) — (i+1,j+1)(i+1,j) — (i,j+1)

/(i+1,j) — (i,j+1)(i,j) — (i+1,j+1)

1

点不是格子，是格点：(N+1) × (M+1) 个，每步走对角线 (±1, ±1)。

2

每格给出两条对角边：顺导线权 0、转 90° 权 1 —— 又回到 0/1 边权。

3

起点 (0,0)、终点 (N,M)，答案就是 dis[N][M]，模板一个字不用改。

4

150 ms 的时限下堆优化 Dijkstra 会被卡；0-1 BFS 是 O(NM) 的稳解。

伪代码 · 格点上的 0-1 BFS

if (N + M) 是奇数: 输出 NO SOLUTION dis[0..N][0..M] = ∞; dis[0][0] = 0 dq = {(0,0)} while dq 非空: (x, y) = dq.pop_front() for (dx, dy) in 四个对角方向: nx = x+dx; ny = y+dy if 越界: continue w = 这一步要转 90° ? 1 : 0 if dis[x][y] + w < dis[nx][ny]: dis[nx][ny] = dis[x][y] + w w == 0 ? 插队首 : 排队尾输出 dis[N][M]

板块 A · 0-1 BFS · 小结

板块 A 记住三件事

边权只有 0 和 1 → 双端队列

0 边插队首、1 边排队尾；全是 1 就退化成普通 BFS。

它为什么对：队列里的距离差 ≤ 1

两端各只差 1，中间自然不超 —— 所以出队顺序天然非降，复杂度 O(V+E)。

先找对“点”，再看边权

小明的游戏：点是格子；电路维修：点是格点。0/1 是建出来的，不是题目白送的。

03

PART 03 · Floyd 的三个视角

一个三重循环，三种用法

原始视角看阶段，矩阵视角看乘法，应用视角看改法。

for k

→

for i

→

for j

f[i][j] = min(f[i][j], f[i][k] + f[k][j])

原始视角矩阵视角应用视角

板块 B · Floyd · 方法

原始视角：一层一层放开中转点

阶段语义：f_k 表示“只允许前 k 个点当中转”

阶段中转点范围这一层算的是什么

f(0)一个都不许只走一条边的距离

f(k)前 k 个点允许借道前 k 个点

f(n)全部 n 个点全源最短路

转移：算 f_k 只许用 f_k−1 的数

f[k][i][j] = min( f[k-1][i][j] , f[k-1][i][k] + f[k-1][k][j] )

f(0)

→

f(1)

→

f(2)

→

…

→

f(n)

①

先抓定义：f_k 是“只允许前 k 个点当中转”的最短路。

②

k 是阶段不是循环：算 f_k 只许用 f_k−1 的数，所以它得在最外面。

③

放内层就是边算边用：算 f[2][1] 时想借道 3，可 f[3][1] 还没算出来。

④

想多扫几遍补救？那就退化成 n 遍 Bellman-Ford，O(n⁴) 白忙一场。

板块 B · Floyd · 手推

手推：5 个点的三轮

就用这张图：5 个点、8 条有向边 —— 1→2:3、1→3:8、2→3:2、2→4:5、3→4:1、3→5:9、4→5:4、5→1:6。

f(0)：只允许走一条边

1

2

3

4

5

1

0

3

8

inf

2

inf

0

2

5

inf

3

inf

0

1

9

4

inf

0

4

5

6

inf

0

k = 1 后：允许经过点 1

1

2

3

4

5

1

0

3

8

inf

2

inf

0

2

5

inf

3

inf

0

1

9

4

inf

0

4

5

6

9

14

inf

0

k = 2 后：允许经过点 1、2

1

2

3

4

5

1

0

3

5

8

inf

2

inf

0

2

5

inf

3

inf

0

1

9

4

inf

0

4

5

6

9

11

14

0

k = 3 后：允许经过点 1、2、3

1

2

3

4

5

1

0

3

5

6

14

2

inf

0

2

3

11

3

inf

0

1

9

4

inf

0

4

5

6

9

11

12

0

①

f(0) 只允许走一条边：够不着的先记 inf（不可达）。

②

放开中转点 k，就把“借道 k”更短的格子改小 —— 高亮的格子就是这一轮被改掉的。

③

三轮走完，矩阵就是全源最短路；k 放在最外层，每格只会被越改越小。

!

盯住这两格

k 每往后一轮，就多放开一个中转点：5→3 从 14 降到 11，1→4 从 8 降到 6。

板块 B · Floyd · 方法

矩阵视角：Floyd 就是 min-plus 乘法

把“最短路”写成矩阵乘法

式子读作

A[i][k] + B[k][j]先走 i→k 一段，再走 k→j 一段

min { … }两条路挑一条，取小的

(A × B) × C = A × (B × C)结合律：先算哪一段都一样

A^k恰好走 k 条边的最短路

所以能倍增：O(n³ log k)

D = I

→

A¹

→

A²

→

A⁴

→

… → A^k

单位阵 I：对角线 0，其余 ∞。Floyd 就是它的 k = n 特例。

①

把“最短路”写成矩阵乘法：加法表示先走一段，min 表示两条路挑一条。

②

好处是结合律：先走 i→k 再走 k→j，和一口气算完是一回事。

③

于是能倍增：A¹、A²、A⁴…… O(n³ log k) 拿到“恰好 k 条边”的最短路。

④

想要“至多 k 条边”，把邻接矩阵的对角线写成 0，站在原地也算一步。

板块 B · Floyd · 方法

应用视角：三重循环换四种改法

#改法三重循环里改哪一行

①传递闭包f[i][j] |= f[i][k] & f[k][j]　（bitset 压位，O(n³/64)）

②无向图最小环ans = min(ans, f[i][j] + w(i,k) + w(k,j))

③最大瓶颈路f[i][j] = max(f[i][j], min(f[i][k], f[k][j]))

④判负环f[i][i] < 0 → 有负环

①

传递闭包：min 和 + 换成 or 和 and，只问通不通；bitset 一压就是 O(n³/64)。

②

最小环：先枚举 i、j < k 用老 f 凑环，再跑第 k 轮更新，不重不漏。

③

瓶颈路：把 min 换成 max、加号换成 min，其余一行都不用改。

④

判负环：跑完检查对角线，f[i][i] < 0 说明有负环经过 i。

板块 B · Floyd · 开场

先看这道题：灾后重建

P1119 · 洛谷经典

地震过后，村庄损毁、公路完好；
只有两端都已重建的公路才能通车。
N 个村庄（编号 0 ~ N−1）、M 条双向公路，
第 i 个村庄在第 t_i 天重建完成。
Q 次询问 (x, y, t)：
第 t 天从 x 到 y 的最短路是多长。
不可达、或 x / y 当天还没重建，输出 −1。

数据范围

1 ≤ N ≤ 200村庄数

M ≤ N(N−1)/2双向公路数

1 ≤ Q ≤ 50000询问数

t 不下降重建时间有序

!

最直接的做法

每个询问都把当天建好的点拎出来，重跑一遍 Dijkstra。

?

卡在哪：Q 到 5×10⁴，重跑就是 10⁹ 起步。可村庄是按时间一个个加进来的 —— 能不能不重算？

板块 B · Floyd · 方法

k 就是那条时间轴

同一个 k，两种说法

Floyd 里的说法灾后重建里的说法

f[k][i][j]：只允许前 k 个点当中转第 k 个重建好的村庄

k 从 1 推到 N时间 t 往前走

k 必须写在最外层村庄只能按时间顺序加进来

询问 (x, y, t)

↓

把 t_k ≤ t 的村庄全部推进来

↓

直接读 f[x][y]，就是答案

1

把「只允许前 k 个点当中转」里的 k，直接换成「第 k 个重建好的村庄」—— 这就是题目里那条时间轴。

2

因为 t 不下降，k 只会往前走、从不回头：每个村庄只当一次中转点，总共 N 轮，O(N³)。

3

询问来的时候先把该建的村庄推进去，再读 f[x][y]；x 或 y 当天没重建就是 −1。

4

这一题讲透了，就再也不会把三重循环的顺序写错 —— k 的顺序是有物理含义的。

板块 B · Floyd · 手推

手推：样例里的 −1、−1、5、4

N = 4，重建时间 t = [1, 2, 3, 4]；每推进一个村庄就跑一轮 Floyd。

推进到新加入的村庄f[0][1]f[0][3]这一轮靠谁中转

初始—∞5只有直接边：0—2—3—1 还串不起来

k = 1村庄 0（t=1）∞50 号连不到 1 号，没有改善

k = 2村庄 1（t=2）∞51 号也连不到 0 号，还是没有路

k = 3村庄 2（t=3）52f[0][1] = 1+4；f[0][3] = 1+1

k = 4村庄 3（t=4）42f[0][1] = f[0][3] + 2 = 4

1

四个询问 (2,0,2) (0,1,2) (0,1,3) (0,1,4)，答案 −1 −1 5 4。

2

前两个都是 −1：一个是村庄 2 还没建，一个是 0 到 1 真的没路。

3

t=3 时 2 号加入，0→2→1 打通，得到 5；t=4 时 3 号加入，0→2→3→1 更短，得到 4。

!

别每次重跑 Dijkstra

5×10⁴ 次询问 × 2×10⁴ 条边 ≈ 10⁹，必超时。
增量 Floyd 总共只跑 N = 200 轮，200³ = 8×10⁶，一秒都用不满。
代价：N 大了就放不下 —— 所以 N ≤ 200 才是这题的前提。

板块 B · Floyd · 写成代码

灾后重建

回到灾后重建：把 Floyd 的三重循环拆开，每来一个村庄只跑一轮。

1

读入时直接把公路填进 f 矩阵：双向、重边取 min，对角线是 0。

2

用一个全局 k 记「已经加进来几个村庄」；每个询问先把 t_k ≤ t 的村庄推进来。

3

加一个村庄 v 就是跑一轮标准 Floyd：f[i][j] = min(f[i][j], f[i][v] + f[v][j])。

4

x 或 y 当天还没重建、或者 f[x][y] 还是无穷，就输出 −1。

伪代码 · 增量 Floyd

读 N, M 读 t[0..N-1] // ① 保证不下降 f[0..N-1][0..N-1] = ∞ for i = 0 .. N-1: f[i][i] = 0 for 每条公路 (i, j, w): f[i][j] = f[j][i] = min(f[i][j], w) 读 Q; k = 0 for 每个询问 (x, y, tt): while k < N and t[k] <= tt: // ② 建好的推进来 for i = 0 .. N-1: // ③ 只跑一轮 for j = 0 .. N-1: f[i][j] = min(f[i][j], f[i][k] + f[k][j]) k = k + 1 if t[x] > tt or t[y] > tt or f[x][y] == ∞: 输出 -1 // ④ 没建好 / 到不了 else: 输出 f[x][y]

板块 B · Floyd · 变体

无向图的最小环

P6175 · 洛谷经典

求一个至少含 3 个点、节点不重复的环，让环上边权和最小。n ≤ 100，m ≤ 5×10³；无向图重边取小的那条，无解输出 No solution.（带句号）。

样例里的最小环四条边边权和

1 — 3 — 5 — 2 — 110 + 20 + 15 + 1661

1

环 = i → … → j 的一条路，再加边 (i,k)、(k,j)；关键是这条路不能碰 k。

2

回到 Floyd 第 k 轮那个瞬间：f[i][j] 恰好是「只经过前 k−1 个点」的最短路，天然不碰 k。

3

所以先凑环、再松弛；顺序反了环里就重复经过 k，是假环。无解记得带句号。

伪代码 · 凑环 + 松弛

读 n, m g[i][j] = f[i][j] = ∞; g[i][i] = f[i][i] = 0 for 每条边 (u, v, d): g[u][v] = g[v][u] = min(g[u][v], d) f[u][v] = f[v][u] = g[u][v] ans = ∞ for k = 1 .. n: for i = 1 .. k-1: // ① 先凑环 for j = i+1 .. k-1: ans = min(ans, f[i][j] + g[i][k] + g[k][j]) for i = 1 .. n: // ② 再松弛 for j = 1 .. n: f[i][j] = min(f[i][j], f[i][k] + f[k][j]) 输出 ans 或 No solution.

板块 B · Floyd · 判据

动手写 Floyd 前，先问自己三句

?

n ≤ 500，而且要全源？

?

只要单源，边权非负？

?

只要单源，边权全是 1？

?

只要连通性，不问距离？

✓

Floyd：n ≤ 500 的全源最短路，邻接矩阵加三重循环，短到能背下来。

~

Dijkstra：只问一个起点，堆优化 O(m log n)，n 到 10⁵ 也不怕。

✓

BFS：边权全是 1 的时候（比如道路拆除），三次 BFS 就够了。

~

并查集 / bitset：只问“通不通”；闭包压位，n 到 3000 也压得动。

!

先看规模，再看要几个源

Floyd 只管“n 小、要全源”这一种，其余三句各有更省的写法。

板块 B · Floyd · 小结

板块 B 小结：记住三件事

视角记住这一句

原始视角k 必须在最外层：f_k 是“只允许前 k 个点当中转”的阶段，挪到内层答案就错了（灾后重建里，k 就是那条时间轴）。

矩阵视角min-plus 乘法满足结合律，A^k 就是“恰好走 k 条边”，可以倍增到 O(n³ log k)。

应用视角记四样：闭包、最小环、瓶颈路、判负环 —— 换个 min/max，就是一道新题（最小环要“先凑环、再松弛”）。

应用视角四样

传递闭包

or / and

最小环

i, j < k

瓶颈路

min 换 max

判负环

f[i][i] < 0

04

PART 04 · 反图与最短路计数

倒着搜一次，正着数一遍

有些问题从终点出发反而好算，有些问题要数清楚到底有几条路。

谁能到 t

→

反图一次 BFS

·

几条最短路

→

最短路图上的 DAG 计数

重边算几条，先看题面

反图三件套最短路图是 DAG 重边算几条

板块 C · 反图 · 开场

先看这道题：寻找道路

P2296 · NOIP 2014 提高组

有向图，每条边的长度都是 1，
给定起点 s 和终点 t。
找一条 s 到 t 的路径，要求：
路径上每个点的所有出边，
指向的点都能（直接或间接）到 t。
在这个前提下让路径最短。
可能有重边和自环；保证 t 没有出边。

数据范围

0 < n ≤ 10⁴点数

0 < m ≤ 2×10⁵边数

边长恒为 1无权图

t 没有出边题目保证

!

最直接的做法

从 s 跑一遍 BFS 求最短路 —— 边长都是 1，这步本身没问题。

?

卡在哪：BFS 边走边判不了“出边都通到 t” —— 你得先知道谁能到 t，可这件事从 s 出发搜不出来。

板块 C · 反图 · 方法

倒过来搜一次，就知道谁能到终点

同一件事，正着搜和倒着搜

想知道正着搜倒着搜

从 s 出发能到谁一次 BFS—

谁能到 t要搜 n 次反图一次 BFS

① 反图从 t 跑一遍 BFS

↓

② 删掉“有出边指向不 ok 的点”的点

↓

③ 正图从 s 只走合法点，BFS 到 t

1

反图：把每条边 u → v 存成 v → u。在反图上从 t 搜一遍，搜到的点就是“能到 t”的点。

2

删点：u 合法 ⟺ u 的每一条出边都指向 ok 的点。注意是“所有”，不是“存在一条”。

3

正图上从 s 只走合法点 BFS；s 自己不合法、或者走不到 t，就输出 −1。

4

三步都是 O(n + m)：反图 BFS + 扫一遍所有出边 + 正向 BFS，比枚举路径便宜得多。

板块 C · 反图 · 手推

手推：两次 BFS 各管什么

样例 2：n = 6、m = 6，边是 1→2、1→3、2→6、2→5、4→5、3→4；s = 1、t = 5。

步做了什么结果

①反图从 t = 5 跑 BFSok = {1, 2, 3, 4, 5} —— 6 进不来

②扫每条出边：谁指向 6？只有 2 → 6非法 = {2}

③正图从 s = 1 出发，只走 {1, 3, 4, 5}1 → 3 → 4 → 5，答案 3

1

反图里从 5 能走到 4 和 2，再往上走到 3、1 —— 这五个点就是“能到 t”的。

2

2 号自己到得了 5，但它还连了一条 2→6，而 6 到不了 5 —— 所以 2 不能用。

3

删掉 2 之后只剩 1→3→4→5 这一条，正好 3 步。

!

样例 1 为什么是 −1

边只有 1→2、2→1、1→3，s = 1、t = 3。
反图从 3 出发一条边都走不了（3 没有入边），ok = {3}；
1 有出边指向 2，而 2 不 ok → 1 自己就非法，直接 −1。

板块 C · 反图 · 写成代码

寻找道路

回到寻找道路：反图定“谁能到”，正图定“走几步”。

1

存边时顺手存一条反向边，得到两张图：原图 G 和反图 R。

2

反图 R 上从 t 跑 BFS，标出 ok[]；题目保证 t 没有出边，所以 t 自己一定 ok。

3

扫每个点的每条出边：只要有一条指向 !ok，这个点就非法 —— 一遍 O(m)。

4

原图上从 s BFS，只走合法的点；s 非法或到不了 t 就输出 −1。

伪代码 · 反图 + 删点 + BFS

读 n, m for 每条边 (x, y): G[x].push(y) // 原图 R[y].push(x) // ① 反图读 s, t ok[1..n] = false BFS(R, 起点 t) -> ok[] // ② 谁能到 t bad[1..n] = false for u = 1 .. n: // ③ 删不合法点 for v in G[u]: if !ok[v]: bad[u] = true; break if bad[s] or bad[t]: 输出 -1 BFS(G, 起点 s, 只走 !bad 的点) // ④ 正向最短路输出 dist[t] 或 -1

板块 C · 反图 · 变体

邮递员送信

P1629 · 洛谷经典

n 个点、m 条单向道路（n ≤ 10³，m ≤ 10⁵，1 ≤ w ≤ 10⁴，任意两点互相可达）。邮局在 1 号点，每次只能带一件，每送完一件都要先回邮局，求最少总时间。

1

每次只带一件，所以总时间 = 各趟去程之和 + 各趟回程之和，两部分分开算。

2

去程好办：从 1 号点跑一次最短路，1 → i 全部到手。

3

回程不能跑 n 次最短路：把每条边反向建一张反图，一次就够。

4

关键一句：反图上从 1 出发的最短路，就是原图上每个点回到 1 的最短路。

两张图各跑一次

跑哪张图一次拿到什么

原图，起点 11 → i 的去程

反图，起点 1i → 1 的回程

伪代码

d1 = 最短路(原图, 起点 1) // ① 1 → i d2 = 最短路(反图, 起点 1) // ② i → 1 print Σ(d1[i] + d2[i]) // ③ i = 2..n

板块 C · 最短路计数 · 开场

再看这道题：最短路计数

P1144 · 洛谷经典

N 个点、M 条边的无向无权图，
顶点编号 1 ~ N。
问：从 1 号点出发，到其他每个点
的最短路各有多少条。
答案对 100003 取模；
到不了的点输出 0。
注意可能有自环，也可能有重边。

数据范围

1 ≤ N ≤ 10⁶点数

1 ≤ M ≤ 2×10⁶边数

答案 mod 100003要取模

有自环、重边读题要抠

!

最直接的做法

先 BFS 求出每个点的最短路长度，再从 1 号点 DFS 数路径。

?

卡在哪：DFS 会指数爆炸（同一条最短路被数很多遍）；而且重边算几条？样例里 4→5 有两条边，1 到 5 的答案是 4，不是 2。

板块 C · 最短路计数 · 方法

最短路图，是一张 DAG

只留下能贡献最短路的边

留下哪些边得到什么

dis[v] = dis[u] + 1最短路图

每条边都从第 k 层指向第 k+1 层一定无环

BFS 的出队顺序天然的拓扑序

数最短路 = 在 DAG 上数路径

↓

cnt[v] = Σ cnt[u]（对所有 dis[u] + 1 = dis[v] 的 u）

1

把所有满足 dis[v] = dis[u] + 1 的边留下来，得到“最短路图” —— 只有它能贡献最短路。

2

这张图里每条边都从第 k 层指向第 k+1 层，所以一定无环，是 DAG。

3

DAG 上数路径不用搜：cnt[v] = Σ cnt[u]，从起点一路推过去就行。

4

最妙的是 BFS 的出队顺序天然就是这张 DAG 的拓扑序 —— 一遍 BFS 同时算出 dis 和 cnt。

板块 C · 最短路计数 · 手推

手推：答案为什么是 1 1 1 2 4

样例：5 个点、7 条边 —— 1-2、1-3、2-4、3-4、2-3、4-5、4-5（4 和 5 之间有两条重边）。

出队discnt这个 cnt 是怎么来的

101起点，只有一条“空路”

2111 → 2

3111 → 3

422cnt[2] + cnt[3] = 2：1→2→4 和 1→3→4

534cnt[4] × 2 = 4：4→5 的两条重边各算一条

1

dis 就是普通 BFS 的层数：0 / 1 / 1 / 2 / 3。

2

cnt[4] = 2：从 2 来一条、从 3 来一条，两条都是最短路。

3

cnt[5] = 4：到 4 有 2 条，4→5 有 2 条边，乘起来 —— 所以样例答案是 1 1 1 2 4。

!

重边算几条，看题面

这题重边各算一条（两条 4→5 是两种走法）。
但 P1608 路径统计里重边必须去重 —— 它数的是“点编号序列”不同的路径。
同一句“不同的最短路”，两题定义不一样。

板块 C · 最短路计数 · 写成代码

最短路计数

回到最短路计数：dis 和 cnt 在同一次 BFS 里一起推出来。

1

无权图，dis 直接用 BFS 的层数；队列出队顺序就是最短路图的拓扑序。

2

第一次访问 v：dis[v] = dis[u] + 1，cnt[v] = cnt[u]，然后入队。

3

之后又遇到 v，且 dis[v] == dis[u] + 1：说明又多了一条最短路，cnt[v] += cnt[u]。

4

N 到 10⁶、M 到 2×10⁶：无向图要存 2M 条边，邻接表别写慢；答案取模 100003。

伪代码 · 一遍 BFS 同时算 dis 和 cnt

读 n, m for 每条边 (x, y): add(x,y); add(y,x) // 无向图 dis[1..n] = -1; cnt[1..n] = 0 dis[1] = 0; cnt[1] = 1; q = {1} while q 非空: u = q.pop_front() for v in 邻接(u): if dis[v] == -1: // ① 第一次到 dis[v] = dis[u] + 1 cnt[v] = cnt[u] q.push_back(v) else if dis[v] == dis[u] + 1: // ② 又一条最短路 cnt[v] = (cnt[v] + cnt[u]) % 100003 for i = 1 .. n: 输出 dis[i] == -1 ? 0 : cnt[i] // ③ 到不了给 0

板块 C · 最短路建模 · 判据

什么时候该“倒着想”

?

问的是“所有点到某个点”的距离？（回程、汇合）

?

问的是“每个点能不能到终点”？（可达性剪枝）

?

问的是“最短路有多少条”？（计数）

?

问的是“从 1 到各点多远”？（单源正着问）

✓

单终点 / 回程：建反图，一次最短路顶 n 次。
邮递员送信就是这么干的。

✓

可达性剪枝：反图先标“谁能到 t”，再删不合法点，最后正向 BFS。寻找道路的三件套。

~

计数：只留 dis[v] = dis[u] + 1 的边，在 DAG 上数；重边算几条要看题面。

✗

单源正着问：直接跑一遍，别折腾反图。

!

反图不是新算法

它只是把“谁能到 t”换成“t 能到谁”—— 图还是那张图，BFS 还是那个 BFS。

板块 C · 最短路建模 · 小结

板块 C 记住三件事

反图：把“谁能到 t”倒过来问

反图从 t 搜一次，就知道所有能到 t 的点；回程、汇合、可达性剪枝都用它。

最短路图是一张 DAG

只留 dis[v] = dis[u] + 1 的边，BFS 的出队顺序天然就是拓扑序 —— 计数就是在这张 DAG 上数路径。

“不同的最短路”要先抠定义

P1144 里重边各算一条；P1608 里重边必须去重。同一句话，两题不一样。

Day4 · 收尾

今天走完了五件事

#板块今天走了什么

①复盘模拟赛四题：路线、纸带、对称差、消消乐。

②板块 A0-1 BFS：0 进队首、1 进队尾；先找对“点”，再看边权。

③板块 A小明的游戏（例题）+ 变体电路维修（格点建图）。

④板块 BFloyd 三视角 + 灾后重建（例题）、最小环。

⑤板块 C反图与最短路计数：反图三件套 + 邮递员送信、最短路图上的 DAG 计数。

下节课

Day5 · 图论与树论（下）：带权并查集、拓展域并查集，再讲最短路建模与分层图。

⚑

回去把上升点列和方格取数的正解各写一遍。

Day5 · 图论与树论（下）

03

并查集与分层图

今天先复盘模拟赛四道题，再讲带权、拓展域并查集与应用，最后把分层图补齐。

模拟赛复盘带权并查集拓展域并查集与应用分层图与最短路建模

并查集也从“连不连通”走到“差多少”—— 还是先把关系说清楚。

带权并查集拓展域并查集

02

PART 02 · 带权并查集

从“连不连通”到“差多少”

并查集不止能判连通：每个点再存一个数，就能记住它和根的关系。

相对关系路径压缩的顺序合并与判据

板块 A · 带权并查集 · 开场

先看这道题：食物链

P2024 · NOI 2001

动物王国里有三类动物 A、B、C：
A 吃 B、B 吃 C、C 吃 A，绕成一圈。
N 个动物各属其中一类，但不知道是哪类。
有人一句接一句说 K 句话：
「1 X Y」表示 X 和 Y 同类，
「2 X Y」表示 X 吃 Y。
问这 K 句里有多少句是假话。

数据范围

1 ≤ N ≤ 5×10⁴动物数

1 ≤ K ≤ 10⁵话的句数

|X|, |Y| < 2³²可能越界

!

最直接的做法

把每句话都记下来，判断时再回头一条条推。

?

卡在哪：普通并查集只会说“在不在一个集合”。可 2 X Y 不是“绑在一起”，是 X 吃 Y —— 有方向；而 A吃B、B吃C、C吃A 还是个环。

板块 A · 带权并查集 · 方法

先给三类动物编个号

三个记号，先认全

记号是什么

type[x]动物 x 属于哪一类：A = 0、B = 2、C = 1

f[x]普通并查集的父亲指针，不变

val[x]x 相对父亲的关系 = type[x] − type[f[x]]（mod 3）

验一遍：这个编号让食物链闭合吗

A 吃 B0 − 2 = −2 ≡ 1✓

B 吃 C2 − 1 = 1✓

C 吃 A1 − 0 = 1✓

先递归拿根

→

再补 val

→

最后改 f

1

给三类动物编号 A = 0、B = 2、C = 1（不是顺着编），规定：type[x] − type[y] ≡ 1 ⟺ x 吃 y。

2

三条边逐条验：0−2 ≡ 1、2−1 = 1、1−0 = 1 —— 环闭合了，这个编号能用。

3

于是“关系”就是一个模 3 的数：0 同类 / 1 x 吃 y / 2 y 吃 x。

4

val[x] 存的是 x 到父亲的关系；find 时一路累加，就成了“x 到根”的关系。

板块 A · 带权并查集 · 手推

手推：1 和 3 到底是什么关系

拿官方样例的前五句话走一遍 —— 关系不是背下来的，是被逼出来的。

步这句话推出什么判定

12 1 2type[1] − type[2] = 1 —— 1 吃 2真

22 2 3type[2] − type[3] = 1 —— 2 吃 3真

32 3 33 吃 3 —— 自己吃自己，不管前面推过什么都假假

41 1 3前两句一拼：type[1] − type[3] = 1 + 1 = 2，要的是 0（同类）—— 对不上假

52 3 1要 type[3] − type[1] = 1；而 −2 ≡ 1 (mod 3) —— 与第 4 步的推断正好对上真

1

前两句都是“吃”，各自给出一条 type 的差 —— 这就是并查集要存的那个数。

2

两条差一拼：type[1] − type[3] = 1 + 1 = 2。没有任何一句话直接说过 1 和 3 的关系，是前两句把它逼出来的。

3

第 4 句要的是 0，推出来是 2 —— 假；第 5 句要的是 1，正好是 1 —— 真。

!

样例剩下两句 & 答案

1 101 1：X = 101 超过 N = 100，直接算假。
1 5 5：5 和自己同类，恒真。
合计假话 3 句，和官方答案一致。

板块 A · 带权并查集 · 方法

合并：val[find(y)] 该填几

手里就有这三样（find 之后）

量含义

val[x]type[x] − type[rx]　（rx = find(x)）

val[y]type[y] − type[ry]　（ry = find(y)）

rel题面直接给：1 X Y → 0；2 X Y → 1（x 相对 y）

ry

—val[ry] = ?→

rx

合并 = 把 ry 挂到 rx 下面

val[ry] = type[ry] - type[rx] type[ry] = type[y] - val[y] type[rx] = type[x] - val[x] val[ry] = (type[y] - val[y]) - (type[x] - val[x]) = (type[x] - type[y]) + (val[x] - val[y]) = (rel + val[x] - val[y]) mod 3

1

find 之后，val[x]、val[y] 都是“到根”的差；rel 是题面那句话给的关系。

2

要填的就是 val[ry] = type[ry] − type[rx] —— 写完这一行，剩下全是代数。

3

把三样代进去，得到 (rel + val[x] − val[y]) mod 3。合并只有这一行。

4

rel 的方向和题面完全一致（都是“x 相对 y”），定死别改；取模记得处理负数。

!

判定也顺手出来了

同根时 type[x] − type[y] = (val[x] − val[y]) mod 3，
和这句话的 rel 比一比：相等就是真话，不等就是假话。

板块 A · 带权并查集 · 写成代码

食物链

回到食物链：把每句话转成一个 rel，剩下的交给并查集。

1

rel 就是题面那句话的关系（x 相对 y）：1 X Y → 0（同类），2 X Y → 1（x 吃 y）。

2

find 里三步顺序不能换：先递归拿根 → 再补 val → 最后改 f，写反了 val 永远是旧的。

3

合并填 val[ry] = (rel + val[x] − val[y]) mod 3；同根时比 (val[x] − val[y]) mod 3 和 rel 相不相等。

4

假话三种：X 或 Y 超过 N、2 X X（自己吃自己）、同根但关系对不上。

伪代码 · 带权并查集判假话

读 n, k f[i] = i; val[i] = 0; ans = 0 find(x): if f[x] == x: return x r = find(f[x]) // ① 先拿根 val[x] = (val[x] + val[f[x]]) % 3 // ② 再补 val f[x] = r // ③ 最后改 f return r for 每句话 (op, x, y): if x > n or y > n: ans++; continue // ④ 越界 if op == 2 and x == y: ans++; continue rel = (op == 1) ? 0 : 1 // 题面直接给的关系 rx = find(x); ry = find(y) if rx == ry: // ⑤ 同根：直接判 if (val[x] - val[y] + 3) % 3 != rel: ans++ else: // ⑥ 不同根：合并 f[ry] = rx val[ry] = (rel + val[x] - val[y] + 3) % 3 输出 ans

板块 A · 带权并查集 · 判据

关系能算就用带权，只有对立就拆点

?

关系是“一个数”吗？差、和、异或 —— 能加减、能取模吗？

?

关系只是“若干类里选一类”吗？只有同类 / 对立，甚至有多个对立类？

?

还想把两种写法互相翻译吗？val 上能做运算的，才能翻译回去。

✓

带权并查集：关系是“一个数”，能加减、能取模。val[x] 存 x 到父亲的这个数，合并算 val[ry] = (rel + val[x] − val[y]) mod 3。典型：模 3 三类关系、异或传递。

✗

拓展域并查集：只有“同类 / 对立”就别硬算 —— x 与 x+n 拆成两个点，合并 x—y+n、x+n—y。典型：敌友、奇偶、二分图染色。

!

一句话

能在 val 上做运算的，用带权；只能数类别的，拆点 —— 两者能互相翻译：模 3 的带权关系 = 把每个点拆成三个点。

板块 A · 带权并查集 · 写法

模板：路径压缩 + 按秩合并

伪代码 · P3367 并查集模板

f[1..n] = 1..n, rk[1..n] = 1 find(x): while f[x] != x: // ① 路径压缩 f[x] = f[f[x]] x = f[x] return x union(x, y): x = find(x), y = find(y) if x == y: return if rk[x] < rk[y]: swap(x, y) // ② 矮的挂到高的 f[y] = x if rk[x] == rk[y]: rk[x] += 1 // ③ 同高才加一层 // 两个优化一起用，均摊才接近 O(α(n))

①

路径折半：find 的路上把自己挂到祖父，多走几趟就贴到根上了。

②

按秩合并：合并时把矮的树挂到高的树下，树高不会失控。

③

两个一起用才接近 O(α(n))；只写一个，大多数题也能过。

路径折半：自己挂到祖父

x

→

f[x]

→

祖父

f[x] = f[f[x]] 之后就少走一层。

板块 A · 带权并查集 · 当堂写热身

当堂写：亲戚（P1551 · OJ #636）

n 个人、m 条亲戚关系、p 次询问（都 ≤ 5000）：亲戚关系可以传递，问给定的两个人是不是亲戚，每行输出 Yes 或 No。

P1551 · 并查集模板

① 并查集只做两件事：union 一个关系、find 问一次连通。
② m ≤ 5000，路径压缩就够，按秩合并先不写也没关系。
③ 要求：5 分钟写完、不调试，写完直接交，看一遍过不过。

要写的就这几行

for 每条关系 (x, y): union(x, y) for 每次询问 (x, y): print find(x) == find(y) ? "Yes" : "No"

5 分钟写完

→

不调试，直接交

→

看一遍过不过

板块 A · 带权并查集 · 小结

板块 A：记住这三句话

① 记什么：val[x] 是到父亲的关系值

find 里必须“先递归拿根 → 再补 val → 最后改 f”，顺序写反 val 永远是旧的。

② 怎么合：把 ry 挂到 rx 下面

val[ry] = (rel + val[x] − val[y]) mod 3；rel 就是题面那句话，方向定死别改。

③ 什么时候用：关系能算就用带权

关系可加、可模 → 带权；关系只有对立 → 拆点。两种能互相翻译。

03

PART 03 · 并查集及其应用

把“对立”变成“连通”

一个点拆成两个点，“不能在一起”就变成了“连在一起”。

拆点敌友关系奇偶与染色

板块 B · 拓展域并查集 · 方法

拆点：一个点当成两个点用

一个点 i 拆成两个域

i

第 0 类

⇒

i+n

第 1 类

一共 2n 个点

把“对立”翻译成“连通”

关系合并哪两个域 / 怎么判断

同类union(i,j); union(i+n,j+n)

对立union(i,j+n); union(i+n,j)

i、j 同类find(i) == find(j)

i、j 对立find(i) == find(j+n)

矛盾！find(i) == find(i+n)

①

为什么拆：并查集只会“合并”，不会表达“这两个不能在一起”。

②

拆完就统一了：所有关系都是“把两个点连起来”，对立也能合并。

③

询问就是查根：同块同类；和“对面那个点”同块，就是对立。

④

代价：点和空间都翻倍，换来的是几行 union、几行 find。

板块 B · 拓展域并查集 · 手推

手推：4 个人，8 个点

4 个人编号 1~4，点 i 表示“i 在第 0 类”，点 i′ 表示“i 在第 1 类”。

操作12341′2′3′4′判定

初始12345678—

朋友 1 211345578同色

朋友 2 311145558同色

敌人 3 411155551异色

问 1 和 4根(1) = 根(4′)→ 敌人

问 2 和 3根(2) = 根(3)→ 朋友

敌人 1 2根(1) = 根(2)→ 矛盾！

①

拆点：把每个人拆成“第 0 类点”和“第 1 类点”，一共 2n 个点。

②

朋友 1 2、朋友 2 3：同类就同类合并，两块各自长大。

③

敌人 3 4：交叉合并（3 连 4′、4 连 3′），两块瞬间对调。

!

矛盾就这么被查出来

同块的人，不能再宣称彼此对立。
{1,2,3,4′} 与 {4,1′,2′,3′} 已经各自成块，再报“敌人 1 2” → 无解。

板块 B · 拓展域并查集 · 方法

奇偶关系：拆“偶点”和“奇点”

x 与 x+n 表示 x 的两种奇偶

x

偶（0）

⇔

x+n

奇（1）

关系：a、b 的奇偶差固定是 w

同奇偶union(a,b); union(a+n,b+n)

不同union(a,b+n); union(a+n,b)

同奇偶find(a) == find(b)

不同奇偶find(a) == find(b+n)

矛盾find(a) == find(a+n)

对比 · 带权并查集：一个点 + 一位权值

find(x)把路上的 w 一路异或上来

关系奇偶差 = w[a] ^ w[b]

①

为什么能拆：奇偶只有两种可能，两种可能各给一个点就够。

②

约束就是合并：差 0 并自己，差 1 并对面，xor 全在 union 里。

③

对比带权：带权只开 n 个点，但 find 要一路异或、还要写对合并。

④

复杂度一样都是 α(n)：拓展域用双倍空间，换一份不容易写错的代码。

板块 B · 拓展域并查集 · 方法

染色和拆点，是同一件事

看什么染色怎么写拆点怎么写

一条边color[v] = color[u] ^ 1union(u,v+n); union(u+n,v)

u、v 同色同一次遍历里染成同一色find(u) == find(v)

u、v 异色color[u] ^ color[v] = 1find(u) == find(v+n)

什么时候失败染色冲突：图里有奇环find(u) == find(u+n) ⇔ 出现奇环

适合什么时候用一次走完整张图，边不能再加边能一条条加，加完随时 O(α(n)) 询问

①

染色是“走一遍图再看颜色”，拆点是“把异色写进并查集”。

②

同色判据：find(u) == find(v)，两个人被推到了同一边。

③

异色判据：find(u) == find(v+n)，u 粘住了 v 的对面点。

④

什么时候失败：要求异色的边两端同块 —— 说明图里有奇环。

=

一句话记住

拆点 = 把染色结果先存进并查集：边加一条记一条，加完随时能问两端什么关系。

板块 B · 拓展域并查集 · 判据

带权还是拓展域？看关系长什么样

两种写法复杂度一样，选哪个只看关系能不能“算”。

?

关系能“加减”、能“取模”吗？（前缀异或、相对距离）

?

关系是若干“对立类”吗？（敌人、两座监狱、异色）

?

要支持撤销、回滚吗？（莫队、线段树分治那种）

✓

关系可加可模：带权并查集，省一半空间。

✓

若干对立类：拓展域并查集，省脑子。

~

要支持撤销：按秩合并 + 栈回滚（不能路径压缩）。

④

两种都能写

挑写熟的那套，别现场推。

板块 B · 拓展域并查集 · 开场

先看这道题：团伙

P1892 · BalticOI 2003

n 个人，两两之间可能是朋友、可能是敌人，
也可能没见过面、没有直接关系。
只知道两条规矩：
朋友的朋友还是朋友；
敌人的敌人也是朋友。
是朋友就一定在同一团，每人只进一个团。
问最多可能有多少个团。

数据范围

2 ≤ n ≤ 1000人数

1 ≤ m ≤ 5000关系条数

F p q / E p q朋友 / 敌人

!

最直接的做法

把关系全存下来，一遍遍地推「朋友的朋友」。

?

卡在哪：新加一条敌对关系，可能把两拨人间接并到一起；存下来反复推是 O(m²)。

板块 B · 拓展域并查集 · 方法

一个人拆成两个点

拆完之后，两种关系都变成“并”

原关系拆点后怎么连

p、q 是朋友union(p, q)

p、q 是敌人union(p, q+n) + union(q, p+n)

p、q 是敌人吗find(p) == find(q+n)

p（本人）

⇅

p + n（对立面）

一共 2n 个点

1

每个人拆成两个点：p 本人和 p + n 对立面，一共 2n 个点。

2

朋友：两边一起并。敌人的敌人会自然落回同一边 —— 这就是拆点的全部魔法。

3

敌人：交叉并 —— union(p, q+n) 不是把 p 和 q 并到一起，而是把 p 并到 q 的对面。

4

最后只数 1 ~ n 里有多少个不同的根，就是最多团数；没关系的人各成一团。

板块 B · 拓展域并查集 · 手推

手推：6 个人，为什么是 3 个团

样例：n = 6，四条关系 E 1 4、F 3 5、F 4 6、E 1 2；拆点后 1 ~ 6 是本人，7 ~ 12 是对立面。

步关系怎么并并完谁和谁在一块

1E 1 4union(1, 4′)、union(4, 1′){1, 4′}　{4, 1′}

2F 3 5union(3, 5){3, 5}

3F 4 6union(4, 6){4, 6, 1′}

4E 1 2union(1, 2′)、union(2, 1′)2 被并进 {4, 6, 1′}

1

前两步各并各的：1 和 4 是敌人，所以 1 和 4′ 一块，4 和 1′ 一块 —— 注意 1 和 4 并没有并到一起。

2

第 4 步的 union(2, 1′) 把 2 送进了 1′ 那一堆，而 1′ 早就和 4、6 在一块 —— 敌人的敌人是朋友。

3

最后只数 1 ~ 6 的根：{1}、{2,4,6}、{3,5} —— 三个不同的根，答案 3。

!

为什么问的是“最多”

没关系的人不会被并到一起，所以每人可以各算一团。
要数的是被迫并在一起的最小块数 —— 题目问的是最多能有几团。
数根的时候别忘了：根可能落在 7 ~ 12 那半边，得用 find(i) 去重，不能只看 find(i) == i。

板块 B · 拓展域并查集 · 写成代码

团伙

回到团伙：开 2n 个点，朋友一起并、敌人交叉并，最后数根。

1

并查集开到 2n：1 ~ n 是本人，n+1 ~ 2n 是对立面。

2

读关系：F p q 并 (p, q)；E p q 并 (p, q+n) 和 (q, p+n)。

3

n ≤ 1000、m ≤ 5000，只写路径压缩就够，按秩合并可以省。

4

数根要去重：根可能落在 7 ~ 2n 那半边，所以扫 1 ~ n 记 find(i)，用 used[] 标记。

伪代码 · 拆点 + 数根

读 n, m f[1..2n] = 1..2n // ① 拆成 2n 个点 for i = 1 .. m: 读 opt, p, q if opt == 'F': // ② 朋友：一起并 union(p, q) else: // ③ 敌人：交叉并 union(p, q + n) union(q, p + n) used[1..2n] = false; cnt = 0 for i = 1 .. n: // ④ 只数 1..n r = find(i) if !used[r]: used[r] = true; cnt++ 输出 cnt

板块 B · 并查集应用 · 开场

先看这道题：道路修复

P14362 · CSP-S 2025 T2

n 座城市、m 条双向道路，原本任意两城相通。
地震把 m 条路全毁了，修第 i 条要 w_i 元。
还有 k 个乡镇：花 c_j 改造乡镇 j，
就能建它到城市 i 的路，费用 a_{j,i}。
乡镇可以改造任意多个，也可以一个都不改。
求让原有 n 座城市连通的最小费用。

数据范围有多大

n ≤ 10⁴城市数

m ≤ 10⁶城市间的路

k ≤ 10乡镇只有 2^k 种选法

w、c、a ≤ 10⁹费用，记得开 long long

!

最直接的做法

枚举改造哪些乡镇，把它和城市一起跑最小生成树。

?

卡在哪：乡镇只有 2^k 种选法，可 m ≤ 10⁶ 条路每次重排太慢。
关键观察：原图本来就连通，城市边只留最小生成树的 n−1 条就够。

板块 B · 并查集应用 · 方法

建模：乡镇 = 花钱买下的新点

目标：让 n 座城市连通 = 最小生成树

花什么钱变成图上的什么

修城市路 i边 (u, v)，权 w_i

改造乡镇 j付 c_j 换来一个点，边权 a[j][i]

枚举买哪些乡镇 Scost(S) = Σ c_j (j ∈ S) + MST(G)

答案min cost(S)，S 可为空集

一条流水线

城市边排序（只排一次）

→

枚举 2^k 个子集

→

归并乡镇边

→

Kruskal 取 min

①

为什么是 MST：让 n 座城市两两连通、总费用最小 —— 正是最小生成树。

②

乡镇当点：付掉 c_j 之后它就是一个普通点，边权 a_{j,i}。

③

为什么能枚举：k ≤ 10，最多 1024 种，每种跑一遍 Kruskal。

④

复杂度：每次扫 10⁴ + 10·10⁴ 条边，1024 次约 10⁸，正好过。

板块 B · 并查集应用 · 手推

拿官方样例算一遍

n=4、m=4、k=2；四条城市路：1–4(6)、2–3(7)、4–2(5)、4–3(4)。

方案挑哪些边费用明细合计

一个乡镇都不买4–3(4) + 4–2(5) + 1–4(6)2–3(7) 多一条，不要15

买下乡镇 1（改造费 1）4–3(4) + 4–2(5) + 1→1(1) + 1→3(2)9 + 1 + 313

买乡镇 2 要 100改造费更贵100 + …更贵

答案取所有组合里最便宜的比不买乡镇的 15 省 213

①

先看“一个乡镇都不买”的基准：城市边里跑一次 Kruskal。

②

再枚举买哪些乡镇：k ≤ 10，最多 1024 种组合，每种把新边并进来重跑。

③

取所有组合里最便宜的，就是 13 —— 比不买乡镇的 15 省 2。

!

算完回头验一遍

买了不连边 = 白花钱，最优解里每个买下的乡镇至少连一条边。

板块 B · 并查集应用 · 写成代码

道路修复

回到道路修复：枚举乡镇子集 + 最小生成树，写成一段。

1

题意换算：要连通的是原有 n 座城市；乡镇是“花钱买的新点”。

2

先算城市内部：m 条边排一次序，Kruskal 只留 n−1 条。

3

枚举子集：k ≤ 10 最多 1024 种，把选中乡镇的边归并进来。

4

每种选法 = 改造费 + MST 结果，取最小；k = 0 就是纯 MST。

伪代码

城市边排序(只排一次) // ① 先排序 Kruskal(E, V): // E 已按 w 升序清空并查集; sum = 0; cnt = 0 for (u, v, w) in E: if find(u) != find(v): union(u, v); sum += w; cnt++ return (cnt == V-1 ? sum : 无穷), used Tcost, Tedges = Kruskal(城市边, n) // ② ans = Tcost // 不买乡镇 for S in 乡镇的 2^k 个子集: // ③ 枚举 fee = Σ c_j (j ∈ S) // 改造费 E = 归并(Tedges, S 的边) // 都有序 V = n + |S| // 点数 ans = min(ans, fee + Kruskal(E, V)) 输出 ans // ④ 取最小

板块 B · 拓展域并查集 · 变体

关押罪犯：一题三种做法

P1525 · NOIP 2010 提高组

N 名罪犯关进两座监狱，M 对仇恨 (a, b, c)；让同一监狱内最大的 c 尽量小。N ≤ 2×10⁴，M ≤ 10⁵。

c 从大到小加边

→

第一条“不得不冲突”的边

→

它的 c 就是答案

做法怎么加边答案在哪

拓展域并查集c 从大到小加边：a 连 b+n、a+n 连 b同块且已连通的那条边 = 答案（一条都没冲突就输出 0）

二分图判定同样从大到小加边，改成看两端颜色；异块就翻转其中一块再合并两端同块且同色 = 答案

二分答案 + 染色二分 X：只留 c > X 的边能二分染色 → X 可行；最小的可行 X 就是答案

板块 B · 并查集及其应用 · 小结

板块 B 记住三件事

① 拆点

把一个点的多种状态拆成多个点，“对立”就变成了“连通”。

② 判据

关系能加减、能取模 → 带权（省空间）；关系是若干对立类 → 拓展域（省脑子）。

③ 三种题三种套路

团伙 = 拆点 + 数根，道路修复 = 2^k × MST，关押罪犯 = 拓展域或二分染色。

单次操作

α(n)

路径压缩 + 按秩合并

!

拆点的代价

点和空间都翻倍，换来的是几行 union、几行 find。

04

PART 04 · 最短路建模与分层图

状态多一维，图就多一层

把“用掉一次机会”画成一条边，算法还是那个算法，状态多了一维。

分层图最短路应用复杂度账

板块 C · 分层图 · 开场

先看这道题：飞行路线

P4568 · JLOI 2011

n 个城市（编号 0 ~ n − 1），m 条航线，
每条航线连接两个城市，坐一次要花 c 块钱。
从 s 飞到 t，途中可以转机，
最多免费坐 k 条航线，问这趟最少花多少。

数据范围有多大

n ≤ 10⁴城市数

m ≤ 5 × 10⁴航线数

k ≤ 10最多免费坐 k 条

0 ≤ c ≤ 10³票价

!

最直接的做法

枚举让哪 k 条航线免费，再跑最短路 —— 组合数数不完。

?

卡在哪：免掉哪几条边要跟着路线一起定，dist 里没地方记这件事。
关键观察：把“还剩几次免费”也记进状态，点就从 n 个变成 n × (k+1) 个。

板块 C · 分层图 · 方法

状态多一维，就复制一层图

原图 n 点 m 边，免费 k 次 → 每点复制 k+1 份

第 0 层

1

2

3

4

5

⇅

层间边 id(u,l) → id(v,l+1) 权 0

第 1 层

1

2

3

4

5

边连谁权

层内边id(u,l) — id(v,l)c

层间边id(u,l) → id(v,l+1)0

编号id(u, l) = u * (k + 1) + l + 1—

①

复制 k+1 层：城市 u（0 ~ n−1）在第 l 层的编号是 u × (k+1) + l + 1（点号从 1 起）。

②

层内边照抄原图：走一条边花一条边的钱，层号不动。

③

层间边权 0，从第 l 层指向第 l+1 层：走它就是用掉一次机会。

④

起点固定在第 0 层（一次没用）；终点 id(t, 0..k) 哪层都算到，答案取各层的最小值。

板块 C · 分层图 · 手推

手推：5 个点、免费 1 次

接着上面的规则：原图 5 点 7 边，起点 1、终点 5，免费坐 1 条边。

dist[层][点]12345

第 0 层（一次没用）034612

第 1 层（用掉一次）30023

①

层号 = 用掉的免费次数：第 0 层一次没用，第 1 层用掉一次。

②

层内边照抄原图，不花次数；层间边从第 0 层指到第 1 层，权 0。

③

终点 5 在两层的 dist 是 12 和 3，取小的：免费一次，12 掉到 3。

④

第 1 层的“1 号点 = 3”不是算错：先走到 2，再免费用掉一次回来。

原图 5 点 7 边，价格在括号里（无向）

1-2(3) 1-3(7) 2-3(1) 2-4(4) 3-4(2) 4-5(6) 2-5(11) 点数 = 5 × 2 层 = 10 边数 = 层内 7×2×2 + 层间 7×2 = 42

答案

min(12, 3) = 3

省了 9

板块 C · 分层图 · 写成代码

飞行路线

回到飞行路线：把“免费 k 次”铺成 k+1 层，再跑一次最短路。

1

建点：每个城市复制 k+1 份，编号 id(u,l) = u × (k+1) + l + 1。

2

层内边：同层的 a、b 之间连两条，权都是 c，走它不花免费次数。

3

层间边：从第 l 层连到第 l+1 层，权 0，走一条就是用掉一次机会。

4

答案：从 id(s,0) 跑一遍，终点在所有层里取最小值。

伪代码

N = n * (k + 1) // ① 铺层 id(u,l) = u*(k+1) + l + 1 读入 (a, b, c): 层内 (a,l)—(b,l) 权 c // ② 层内 (b,l)—(a,l) 权 c 层间 (a,l)→(b,l+1) 权 0 // ③ 层间 (b,l)→(a,l+1) 权 0 Dijkstra( id(s,0) ) // ④ 跑一遍 ans = min dist[各层] // ⑤ 取小输出 ans

板块 C · 分层图 · 方法

先算复杂度账，再决定铺不铺

规模 = 原图 × 层数，先估一遍

原图

n 点 2m 弧

×

层数

k + 1

=

k = 1e5

1e9 点

铺不动

规模公式

点数(k + 1) × n

边数2m(k+1) + 2mk（层内 + 层间）

时间O( 2m(2k+1) log )（堆优化）

P4568 实算：n ≤ 1e4、m ≤ 5e4

点数 11 × 1e4 = 1.1e5 边数 2×5e4×21 = 2.1e6 跑得动：2.1e6 条边一秒内

①

点数和边数都乘 (k+1)：先把数算出来，超标就趁早换思路。

②

这题是 1.1e5 个点、2.1e6 条边，堆优化 Dijkstra 一秒内跑完。

③

k 一大就不能真铺层：层数是 k+1，点数会直接把内存撑爆。

④

换思路：① 目标是最小化最大值时可二分答案；② 只要奇偶两态 → 层数 2。

板块 C · 分层图 · 开场

先看这道题：旅游巴士

P9751 · CSP-J 2023 T4

景区有 n 处地点、m 条单向道路，
1 号地点是入口，n 号地点是出口。
每 k 单位时间有一班车到入口、
同时有一班车从出口离开景区。
每条路走一次恰好 1 单位时间，
且只有不早于 a_i 时刻才能通过。
路上不能停留，入口出口也不能等，
走不动就整趟晚一班车。
他到入口、离开出口的时刻都得是 k 的倍数。

数据范围

2 ≤ n ≤ 10⁴地点数

1 ≤ m ≤ 2×10⁴单向道路数

1 ≤ k ≤ 100班车间隔

0 ≤ a_i ≤ 10⁶这条路最早能过的时刻

!

最直接的做法

从入口跑一遍 BFS —— 可每条路都有开放时间。

?

卡在哪：早到反而过不去，“第一次到就是最近”不成立了。
要解决什么：把“现在几点了”也记进状态 —— 这就是分层图。

板块 C · 分层图 · 手推

手推：样例里的 6 是怎么来的

拿样例 5 5 3 跑一遍状态表：状态是 (点, 时刻 mod 3)，dis 记最早到达时刻。

dis[(点, 时刻 mod 3)]，起点 (1, 0) = 0

r ＼ uu = 1u = 2u = 3u = 4u = 5

r = 00∞∞∞6

r = 1∞11∞∞

r = 2∞∞∞52

1

从 (1, 0) 出发：1→2、1→3 的开放时间都是 0，直接走，1 时刻到 2 和 3。

2

3→4 要 ≥ 3 才能过：1 时刻不行，把整趟推后一个 k，4 时刻上路、5 时刻到 4。

3

4→5 直接走，6 时刻到出口；6 是 3 的倍数，读到 (5, 0)，答案就是 6。

样例 · n = 5 m = 5 k = 3

1→2(0) 2→5(1) 1→3(0) 3→4(3) 4→5(1) 6 6 = 3（到入口时刻）+ 3 条边

!

表里还有个更早的值

表里 (5, 2) = 2 更早，但 2 不是 k 的倍数 —— 出口只在 r = 0 那层算数。

板块 C · 分层图 · 写成代码

旅游巴士

回到旅游巴士：把“时刻 mod k”当成层，剩下的就是分层图上的最短路。

1

状态 (点, 时刻 mod k)：n × k 个，n ≤ 10⁴、k ≤ 100，一共 10⁶ 个，存得下。

2

起点是 (1, 0)（0 时刻就有一班车到入口），答案是 (n, 0)：离开时刻得是 k 的倍数。

3

走一条边：能走就直接走、时刻 +1；走不动就把整趟往后推一个 k，等于坐晚一班车。

4

推后不改变余数，所以层不变；每个状态可能入队多次，但只会被最终确定一次。

伪代码 · 分层图最短路

下面的代码用队列写法，出队时跳过旧副本，结果一样。

// ① 状态 = (点, 时刻 mod k)，共 n × k 个 dis[1..n][0..k-1] = ∞ dis[1][0] = 0; q = {(1,0)} while q 非空: (u, r) = q.pop(); t = dis[u][r] for v, a in 边(u): // ③ 走不动就推后一个 k t2 = t // ③ 每条边各算各的 if t2 < a: t2 = t2 + (a-t2+k-1)/k*k nd = t2 + 1 if nd < dis[v][nd % k]: // ④ 松弛 dis[v][nd % k] = nd q.push((v, nd % k)) print dis[n][0] // ② 离开时刻要是 k 的倍数

板块 C · 分层图 · 变体

加工零件：层数 = 2 的分层图

Day3 板块 C 讲过的加工零件（P5663，CSP-J 2019 T4）：
n 位工人、m 条双向传送带，工单问 (a, L)。
当时的状态是 (工人, 步数奇偶) —— 一共两层。

查询看 d[a][L 的奇偶] ≤ L 就 Yes；但 1 号没有传送带时要输出 No

同一套分层图，两个下标

对比加工零件旅游巴士

层是什么步数奇偶时刻 mod k

层数2k

1

那两层的下标不是“用掉几次机会”，而是“走了奇数步还是偶数步”。

2

每走一步都从 (u, p) 落到 (v, p⊕1)，没有层内边；本质上还是多一维状态。

3

所以不重复讲：层数 = 2 的分层图就是它，今天的旅游巴士是层数 = k 的那版。

板块 C · 最短路应用 · 开场

再看这道题：道路拆除

P5683 · CSP-J 2019 江西

A 国有 n 座城市，1 号城市是首都，
m 条双向道路，每条路走一次都是 1 单位时间。
要拆掉尽量多的路，但拆完后从首都出发，
到 s₁ 的时间 ≤ t₁、到 s₂ 的时间 ≤ t₂（两个条件独立）。
问最多能拆几条路；做不到输出 −1。

数据范围有多大

n, m ≤ 3000城市数、道路数

1 ≤ x, y ≤ n一条路的两个端点

2 ≤ s₁, s₂ ≤ n两个目的地不是首都

0 ≤ t₁, t₂ ≤ n两个时间限制

!

最直接的做法

枚举拆掉哪些边 —— 2^m 种拆法，m = 3000，想都别想。

?

卡在哪：拆哪几条、拆完两条最短路还够不够短，这两件事绞在一起。
关键观察：反过来算 —— 问“最多拆”＝问“最少留”，留的就是两段最短路。

板块 C · 最短路应用 · 方法

最短路不是答案，是干活的工具

最多拆几条 = m − 最少留几条；留下的部分只有两种形状

1 → s₁

∥

1 → s₂

① 各走各的，从不碰头

形状留边数怎么算

①d1(s1) + d1(s2)

②d1(v) + dv(s1) + dv(s2)（共享段 + 两条分岔段）

1 → v 共走一段

→

v → s₁

/

v → s₂

② 再在 v 分岔

枚举交点 v，取最小值

答案 = m − 最小留边数

①

最短路在这里只是零件：答案是“枚举”出来的，不是跑出来的。

②

形状只有两种：两条路完全不碰，或者先共走一段再分岔。

③

于是只要求出每个点到 1、s₁、s₂ 的距离，再枚举交点取最小值。

④

条件别忘了：共享段加两条分岔，都要塞进 t₁、t₂ 两个时间限制里。

板块 C · 最短路应用 · 写成代码

道路拆除

回到道路拆除：三遍 BFS 拿距离，再枚举交点。

1

题意换算：最多拆几条 = m 减去最少留几条，留的边要撑起两条路。

2

形状：两条路先共走 1 → v，再在 v 分成两段，v 就是交点。

3

无向图距离对称：从 1、s₁、s₂ 各跑一遍 BFS，就凑齐三个距离。

4

枚举交点：两条路都塞得进时间限制的，留边数取最小；没有就 −1。

伪代码

BFS(1) -> d1[] // ① 首都 BFS(s1) -> dA[] // ② s1 BFS(s2) -> dB[] // ③ s2 best = 正无穷 for v = 1 .. n: // ④ 枚举 v if d1[v]+dA[v] > t1: continue if d1[v]+dB[v] > t2: continue keep = d1[v] + dA[v] + dB[v] best = min(best, keep) if best 无穷: 输出 -1 // ⑤ 无解输出 m - best // ⑥ 答案

板块 C · 分层图 · 判据

什么时候该铺层

?

多出来的那一维是什么？（用掉几次机会 / 奇偶 / 别的状态）

?

层数要几层？（用掉 k 次 → k+1 层；只有奇偶 → 层数固定 2）

?

铺完有多大？点数和边数都要乘层数，先估再铺。

?

k 很大还铺得动吗？（目标是最小化最大值 → 二分答案判定）

✓

用掉 k 次：铺 k+1 层图。

✓

状态多一维：就复制一层图。

✓

只有奇偶：层数固定 2。

~

k 很大：二分答案判定（目标是最小化最大值时）。

!

先想清楚

先找“多出来的那一维是什么”，再决定层数和做法。

板块 C · 分层图 · 小结

板块 C 小结

分层图

“用掉一次机会”就复制一层，层间权 0。飞行路线、旅游巴士都是这一招。

最短路应用

道路拆除：最多拆几条 = m − 最少留几条；三遍 BFS + 枚举分叉点 —— 最短路只是零件。

复杂度账

规模 = 原图 × 层数；k 大时：目标是最小化最大值可二分；只有奇偶两态就把层数固定成 2。

!

最短路常常只是零件

真正的答案靠枚举和建模凑出来。

Day5 · 收尾

今天走完了五件事

①

复盘模拟赛四题：加密货币、素数和、声音、道路。

②

板块 A 带权并查集：val[x] 记到父亲的权，先拿根再改 val。

③

板块 B 拓展域并查集（拆点、敌友、奇偶）+ 并查集应用：团伙、道路修复、关押罪犯。

④

板块 C 最短路建模与分层图：飞行路线、旅游巴士、道路拆除（反图已在 Day4 讲过）。

⑤

回去把食物链和团伙的正解各写一遍 —— 带权、拓展域两套写法都要能默出来。

结课

国庆集训的模拟赛与专题课到此结束，回去把这三天讲过的例题正解各打一遍。

⚑

写完先对拍，再交题。