3 月图论讲课专题题目

 

ARC092F Two Faced Edges

题目大意

• 有一个 个点 条边的有向图。保证图中不存在重边和自环。
• 试判断将每条边反向，其他边不变的情况下，图中强连通分量的数量是否改变。
• 若改变，输出 diff，否则输出 same。
• ，。

解答

因为 ，所以我们可以枚举每一条边，然后在很小的时间复杂度内判断它的答案。

因为关心的是强连通分量的数量，所以对于边 ，就有以下两个需要关心的量：

1. 是否有从 到 的路径。
2. 是否有不经过 的单向边的从 到 的路径。

然后分类讨论：若两个条件都满足，反向后 和 依然强连通。若两个条件都不满足，反向后 和 依然不强连通。所以数量不变。

若满足条件 1 而不满足条件 2，那么反向前， 和 强连通，反向后就断成了两个强连通分量了。所以数量改变。若满足条件 2 而不满足条件 1，那么同理，反向前不强连通，反向后强连通，就是两个强连通分量缩减为了一个。所以数量改变。

那么如何快速判断这两个条件是否满足？条件 1 是好判的，DFS 加邻接矩阵。那么对于条件 2，我们枚举每一个点 DFS 的时候，先 DFS 一遍，记录每一个点通过 的哪一个出点到达。然后将 的出点的顺序反向，再 DFS 一次，记录每一个点通过 的哪一个出点到达。若不同，则满足。否则不满足。

P4630 铁人两项

题目大意

给定一个无向图，求有多少个符合条件的点对 ，满足 ，并且 到 的一条简单路径上经过了 。

，。

解答

那么我们就将原图转化为一棵圆方树。具体的，圆方树上面分为两种点：圆点和方点。圆点就是原图上所有的点，方点则是一种虚点，每一个点双连通分量都连接着一个方点。

那么，我们就可以在求点双的同时把圆方树建出来。然后就变成了一个树上问题。对于原图中的每一个点，我们就要求：有多少条路径经过了这个点？

于是乎，对于圆方树问题，有一个常用 trick：给每一个点赋上特定的点权，然后再去做树上问题。那么这道题，就可以将圆点点权赋为 ，方点点权赋为与其连接的圆点个数。

然后就在树上统计有多少条两端点为圆点的路径经过了这个点（注意 和 是两个不同的点对，所以要 ），然后再乘上该点的权值作为该点的答案。最后将这些点的答案加起来即为总的答案了。

P1967 货车运输

题目大意

A 国有 座城市，编号从 到 ，城市之间有 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

，，。

解答

一道 Kruskal 重构树的模板题。

Q：Kruskal 重构树是什么？

Kruskal 重构树是一个可以维护两点在最小生成树上的最大边权的树。可以在 Kruskal 算法建最小生成树的同时构建。

具体的，在使用 Kruskal 算法建最小生成树，是可以通过并查集实现的。我们对于每一个连通块记录这个连通块代表的节点。最开始设置其为 ，和 一样。当合并两个连通块时，我们就对于这两个连通块，新开一个节点，将这个点点权赋值为这条边边权。然后将这个新点和原来的两个连通块连边。最后将这个新连通块的代表的节点设为这个新点。

这样，就会得到有 个实点、 个虚点的一棵树。欲求两个点在最小生成树的最大边权，那么求这两个点在树上 LCA 的点权即可。

最大生成树的最小边权同理。

这道题就是让我们求最大生成树的额最小边权。按照上面的方法构造即可。

P9352 训猫

题目大意

有 个猫爬架，编号从 1 到 。第 （）个架子的高度是 。架子的高度是 和 之间的不同整数，包括 和 。有 对架子彼此相邻。对于每个 （），第 个架子和第 个架子彼此相邻。从任意一个架子开始，总能通过不断移动到相邻的架子来到达所有其它架子。

一开始，一只猫待在高度为 的那个架子中。

接下来对这只猫进行锻炼。在锻炼中，我们每次选择一个架子并在其上放置障碍物。但是，我们不能在已经放置障碍物的架子上再放置障碍物。在此过程中，会发生以下情况。

• 如果猫不待在选定的架子中，则什么也不会发生。
• 如果猫待在选定的架子中，并且与选定架子相邻的每个架子上都有障碍物，则锻炼结束。
• 否则，猫将沿最短路径前往，仅通过移动到相邻的架子且不经过放置过障碍物的架子，能到达的所有架子中，高度最高的那个。

给定每个架子的高度和架子彼此相邻的方式，编写一个程序，计算如果我们适当放置障碍物，猫最多需要移动多少次。从一个架子移动到相邻的架子被称为一次移动。

。

解答

其实，这只猫的路线是可以被固定的。因为你可以在你要选的那条路线的旁边都放上障碍。

但是有一个限制：就是说你选的路线 中间不能存在任何大于 或 的。所以，我们可以将所有点按照高度，从小到大排序（实现方法的一种是在建图时，将所有点的编号转化为 ）。这样，选择的顺序就是固定的了。

然后就开始树上转移：按照高度从小到大遍历所有的点：设现在遍历的点为 。

枚举 的所有出边，看有哪些点的权值是小于 的（这在之前是被遍历过的）。然后就看它要跳哪一个子树去。因为跳子树肯定是跳这个子树中值最大的点，所以我们可以使用并查集，来维护现在哪些点目前连通了的，以及当前连通块的最大高度。

我们设 为目前从 开始跳，能跳的最大的距离。 为 所属的连通块的最大高度。那么就可以转移：。然后取所有和 有边相连的、并且值小于 的 ，将 和 在并查集上合并。最后取 即可。

AT_cf17_final_j Tree MST

题目大意

给定一棵 个节点的树，现在有一张完全图，两点 间边长为 ，其中 表示树上两点的距离（ 值初始给定，树上边权为 ）。

求完全图的最小生成树的边权和。。

解答

这道题需要用到 Boruvka 算法求最小生成树的相关知识。

Q：如何使用 Boruvka 算法求最小生成树？

首先，我们将原图分为 个连通块。每一个点为一个连通块。

然后，对于每一个连通块，我们找一条一个端点在该连通块内，另一个端点在该连通块外，并且边权最小的一条边。所有连通块找完了之后就通过这一条边合并两个连通块。

一直执行这个操作直到最后只剩下一个连通块。这个连通块就是原图的一种最小生成树。这种算法在求边很多的稠密图的最小生成树时非常有用。因为最多只会执行 轮操作（每一轮操作都会使最小连通块的 为它原来的两倍）。

然后，对于这道题，我们也可以使用 Boruvka 算法的类似思想。对于两棵子树合并成的一棵树，我们可以先找一个点 DFS 一遍（DFS 的同时赋 ），然后找出最小的 的 。这个点肯定是连接这两棵树的最小边的一个端点。然后再遍历合并过后的这棵树，令现在遍历的点为 ，那么定边 。有些边肯定是比原来长度大的，没关系。因为这一次 DFS 只用求那最关键的一条边，其他边可以作废。

然后对于这两棵树，我们就可以再递归下去……就变成了一个经典的点分治问题。每次 DFS 的起始点其实就是这棵树的重心。然后就得到了 条边。最后可以使用 Boruvka 算法或是暴力的 Kruskal 来求最小生成树。前者在点分治的同时求最小生成树可以达到 的时间复杂度，后者好实现，但是时间复杂度为 ，但是也能过。

ARC084B/ABC077D Small Multiple

题目大意

给定一个整数 。求一个 的正整数倍 ，使得 的数位累加和最小。

。

解答

这道题可以跑同余最短路。因为我们要求 的正整数倍，所以就要跑 意义下的同余最短路。具体如何构建？

我们就定节点 ，分别代表 的 种情况。然后连两种边：

1. 操作，将点 和点 连一条有向边，边权（代价）为 。
2. 操作，将点 和点 连一条有向边，边权（代价）为 。

这种有可能会出现一些不优的情况，但是最优的情况一定是存在的。而因为求的是最优，所以这样建图是合法的。

最后，因为是 的正整数倍，不能是 ，所以可以新开一个点 ，然后再连一条 的有向边，边权为 。然后跑 的最短路即可。

P7669 月票购买

题目大意

JOI 君住在一个有 个车站的城市。车站编号为 至。编号为 至 的有 条铁路。铁路 （）双向连接 站和 站，票价为 日元。
JOI 君住在 站附近，去 站附近的 IOI 高中。他打算买一张连接这两个站的通勤票。当他购买通勤票时，他需要选择一条成本最低的 站和 站之间的路线。使用此通勤票，他可以沿任何方向乘坐所选路线中包含的任何铁路，而无需额外费用。
JOI 君经常去 站和 站附近的书店。因此，他想买一张通勤票，这样从 站到 站的费用可以降到最低。
当他从 站移动到 站时，他首先选择了一条从 站到 站的路线，那么他需要支付的车费是：

• 日元：如果铁路 包含在他购买的通勤票时选择的路线中，或者，
• 日元：如果铁路 不包含在他购买通勤票时选择的路线中。

上述票价的总和就是从 站到 站的成本。
他想知道如果他在购买通勤票时选择合适的路线，从 站到 站的最低成本。

，。

解答

可以发现，这个人走的路线一定是先走一段需要花钱的路，然后再走一段免费的路，最后再走一段花钱的路。中间的路不可能为 2 段。因为选代价为 的路一定是更优的。

那么我们就可以建分层图，第一层和第三层为原图，第二层暂定为免费的路线。那么现在要求的就是哪些路线是 的最短路。

对于每一个边 ，若 ，那么边 就可以被算作 的最短路里面。还有一种情况，若 ，那么边 就可以被算作 的最短路里面。

但是现在有一个问题，现在求出了最短路有哪些边了，但是可能会有这个人走最短路走到了一个点，但是又沿着另外一条路线往回走的情况。由题意看出这个是不合法的，所以要把中间的第二层拆为两层，记其为 2·1 和 2·2 层。层 2·1 存单向边，存哪一些边在 的最短路里面，层 2·2 存单向边，存哪一些边在 的最短路里面。

最后将第一层的点和第 2·1 层、第 2·2 层的点连单向边，代价为 ；第 2·1 层和第 2·2 层和第三层的点连单向边，代价为 。然后求第一层的 和第三层的 的最短路即可。

P9351 迷宫

题目大意

给定一张 的地图，其中 . 可以走，而 # 不能走。一次操作可以将 的正方形范围内所有点变成 .，给定起点和终点，求最少需要几次操作使得起点和终点连通（只能上下左右移动）。

，。

解答

假设现在某个地方。那么可以花费 的代价走向旁边 4 连通的白点。

而假设现在旁边有一个黑点，那么可以花费 的代价，使接下来的 次行走的代价都为 ，并且可以 8 连通游走。

那么就可以使用 01 BFS 来解决这道题。

Q：什么是 01 BFS？

01 BFS 是一种解决边权只有 0 和 1 的最短路问题的方法。这种的复杂度只有 。点数级别。非常爽。

我们使用一个双端队列，然后每次从前取出。若接下来的边权为 ，那么就将其更新后，push_back 进队列。若接下来的边权为 ，那么就将其更新后，push_front 进队列。

这样做是正确的，因为你取的是现在最优的 ，若边权为 ，那么依然为现在最优，继续使用。否则就不优，push_back。并且 的单调性也是显然的。

P3231 消毒

题目大意

最近在生物实验室工作的小 T 遇到了大麻烦。 由于实验室最近升级的缘故，他的分格实验皿是一个长方体，其尺寸为 。为了实验的方便，它被划分为 个单位立方体区域，每个单位立方体尺寸为 ，并用 标识一个单位立方体。这个实验皿已经很久没有人用了。现在，小 T 被导师要求将其中一些单位立方体区域进行消毒操作（每个区域可以被重复消毒）。

而由于严格的实验要求，他被要求使用一种特定的 F 试剂来进行消毒。 这种 F 试剂特别奇怪，每次对尺寸为 的长方体区域（它由 个单位立方体组成）进行消毒时，只需要使用 单位的 F 试剂。F 试剂的价格不菲，这可难倒了小 T。

现在请你告诉他，最少要用多少单位的 F 试剂。

，。

解答

根据 F 试剂的消毒原理，最优的选法肯定是 。

首先先不分析 3 维，先分析 2 维。

二维的情况相当于是，假设这里有一个点 需要消毒，那么就必须选第 行或是必须选第 列。我们就可以将其看为一个二分图，左边为第 行，右边为第 列。 就相当于是给左边的 和右边的 连了一条边。

那么现在问题就转化为：选一些点，让每一条边都至少有一个点被选。这就是二分图最小点覆盖问题。

根据 Konig 定理，二分图最小点覆盖等于二分图最大匹配。

现在跳到 3 维。由于是没有三分图最小点覆盖的这种东西的，所以我们要尽可能地将其转化为 2 维问题。

看数据范围，，所以可以根据边长排序并重组点的 坐标，得到最小的那个 一定 。所以 是极小的。那么就可以状态压缩，枚举哪些 坐标被喷了。然后把所有 不在这个状态里面的点拿出来建一个二分图，然后跑最大匹配，再加上 即这个状态的答案。最后答案就是所有答案的最小值。

P3825 游戏

题目大意

小 L 计划进行 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 、、 表示。地图一共有四种，分别用小写字母 、、、 表示。

其中，赛车 不适合在地图 上使用，赛车 不适合在地图 上使用，赛车 不适合在地图 上使用，而地图 则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 张。

场游戏的地图可以用一个小写字母组成的字符串描述。例如： 表示小 L 计划进行 场游戏，其中第 场和第 场的地图类型是 ，适合所有赛车，第 场和第 场的地图是 ，不适合赛车 ，第 场和第 场的地图是 ，不适合赛车 ，第 场和第 场的地图是 ，不适合赛车 。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 来描述，表示若在第 场使用型号为 的车子，则第 场游戏要使用型号为 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 -1。

，，。

解答

首先， 是好做的。设某位置的字母为 a，那么就可以设状态为 该位置选 B 或是该位置不选 B（即选 C）。对于字母 b、c 同理。

连边也是好连的，但是有一种特殊情况，设原序列为 ba，但是有 1 C 2 A 的限制，那么这种情况就是只要选了 1 C 就不合法了。那么就要连一种最能想得到的不合法的情况：1 C 1 B。只要你选了 1 C，那么就选 1 B，就一定不合法。最后跑 2-SAT 即可。

但是现在 ，由于 3-SAT 是及其不容易做，相当于是没有做法的，所以我们一定要尽力将其转化为 2-SAT。那么就枚举这 个 x， 它是 a 还是 b（注意到 c 是没有必要的，因为 a 包含了「选 B」和「选 C」，b 包含了「选 A」和「选 C」，所以也就没必要搞个 c 了）。然后再跑 2-SAT，最后随便输出一个合法方案即可。

CF1404E Bricks

题目大意

你有一个 （）的格子纸，格子要么涂黑（#）要么涂白（.）。你需要用若干个长为一，宽为任意正整数或者宽为一，长为任意正整数的长方形去覆盖所有黑色格子，要求不能盖到白色格子上，不能盖到其他长方形上，不能盖出格子纸的边界，求最少用多少个长方形。

数据保证至少有一个黑色格子。

解答

一种经典的 trick 就是网格图可以被转化为二分图。

这道题就可以将连接相邻（指边相邻）的两个点的边看为二分图上的点。然后设竖着的点在左边，横着的点在右边。

因为若你选了竖着的点，相当于是你选了上、下两个原图中的点组成竖着的矩形。若你选了横着的点，相当于是选了左、右两个原图中的点组成横着的矩形。对于每一个点，选了竖着的就不能选横着的。那么就可以连边，建二分图，然后求这个二分图的最大独立集。

根据 Konig 定理，二分图最大独立集等于顶点数减去最大匹配。

然后再用所有点的个数减去最大独立集就是最少用几个长方形了。

P3227 切糕

古法酿题，越酿越香（？

题目大意

出于简便考虑，我们将切糕视作一个长 、宽 、高 的长方体点阵。我们将位于第 层中第 行、第 列上的点称 ，它有一个非负的不和谐值 。一个合法的切面满足以下两个条件：

• 与每个纵轴（一共有 个纵轴）有且仅有一个交点。即切面是一个函数 ，对于所有 ，我们需指定一个切割点 ，且 。

• 切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 和 ，若 ，则 ，其中 是给定的一个非负整数。

可能有许多切面 满足上面的条件，小 A 希望找出总的切割点上的不和谐值最小的那个。

。

解答

老题。

我们对于每一个 ，我们可以建图：

每一个 都向 连边（令源点为 ），容量为 。然后 再向汇点连一条边，容量为 。然后我们就要选现在要在每一个 割一条边，求最小割。

但是还有一些限制：即相邻的点的高度必须 。那么就可以对每一对相邻的 和 ，连 。直到连到 为止。这样就可以保证相邻两个点的割的 差小于等于 了。

然后跑最小割，即为答案。

CF724E Goods Transportation

题目大意

给一张图，除了 以外有 个点。

向每一个点 连容量为 的边，每一个点 向 连 的边。

对于任意 ， 向 连 的边。求最大流。

。

解答

首先，将最大流转化为最小割。

我们有两个集合 ， 中包含 和一些节点， 中包含 和另一些节点，如何求最小割？

$$\begin{aligned} &\sum _{i \in A} s_i + \sum_{i \in B} p_i + \sum_{i \in A, j \in B} c \\ = & \sum_{i \in A} s_i + \sum_{i \in B}p_i + (|A|-1)\times (|B-1|)\times c \end{aligned}$$

那么我们可以设 为考虑前 个元素，其中有 个点在 集合、剩下 个元素全在 集合里的最小割。那么分两种情况：

• ，。
• ，。

值即为两者之间取最小值即可。

最后答案即为 时， 序列的最小值。需要用滚动数组，不然会 MLE。