同学们今天我们要去一个神奇的图论王国探险这个王国里有许多城市城市之间有道路连接。每条道路都带着一个特殊的符号道路走过它权值增加 1。-道路走过它权值减少 1。我们的任务是从城市s出发走到城市t让路线的权值尽可能小。一、先理解题目什么叫“平衡路线”假设有一条路线s --()- A --(-)- B --()- t这条路线经过2 条道路1 条-道路。路线权值定义为因此∣2−1∣ 1如果另一条路线经过3 条道路3 条-道路那么它的权值就是∣3−3∣0权值为 0说明正负道路数量相等路线达到了完全平衡。所以题目并不是单纯寻找经过道路最少的路线而是寻找正负道路数量之差的绝对值最小的路线。题目还特别说明允许重复经过顶点和边。这一点非常重要因为我们可以在道路上来回走动改变正负道路的数量。二、程序使用了哪些工具程序中有几个重要数组int h[N], e[M 1], ne[M 1], w[M 1]; int q[N], d[N], c[N];我们用小学生容易理解的方式来认识它们。变量可以把它想象成作用h[]每个城市的道路目录找到从某个城市出发的道路e[]道路终点记录记录一条道路通向哪个城市ne[]道路目录的下一页把同一个城市的道路连接起来w[]道路的符号标签记录道路权值是1还是-1q[]BFS 排队队伍存放等待处理的城市d[]路程记录本记录从起点到某个城市的最少道路数c[]红蓝颜色卡给城市进行二分图染色其中d[]和c[]是理解后面几个空的关键。三、第 34 题① 应该填什么选项A.op[0] ? 0 : 1B.op[0] C.op[0] ? 1 : -1D.op[0] - ? 1 : 0正确答案C。1. 题目中的代码std::cin a b op; int z ①; add(a, b, z); add(b, a, z);这里的op保存道路的符号。例如输入2 5 表示城市 2 和城市 5 之间有一条道路。程序需要把符号转换成数字方便后面计算。2. 为什么对应 1-对应 -1题目定义经过一条道路正道路数量增加 1经过一条-道路负道路数量增加 1。因此可以把道路权值设置为 → 1 - → -1C 中的三目运算符可以这样写op[0] ? 1 : -1它的意思是如果 op[0] 是 z 1 否则 z -1所以int z (op[0] ? 1 : -1);第 34 题选 C。记忆口诀正号变 1负号变 -1路线权值就能用加法计算啦四、第 35 题② BFS 的循环条件是什么选项A.hh nB.tt nC.hh ttD.hh tt正确答案D。1. 先认识 BFS 队列BFS 是广度优先搜索。可以把它想象成城市里的探险队从起点出发先处理离起点近的城市再逐层向外探索。程序使用队列int hh 0, tt 0; q[tt] s;这里hh队头位置表示下一个要处理的元素tt队尾位置表示下一个可以放入元素的位置。开始时hh 0 tt 0把起点s放进队列q[tt] s;执行后hh 0 tt 1队列里有一个城市等待处理。2. 为什么使用hh tt只要队头还没有追上队尾就说明队列里还有城市没有处理。因此while (hh tt)意思是只要队列不为空就继续搜索。当hh tt说明所有已经入队的城市都处理完了队列为空搜索结束。3. 为什么其他选项不合适hh n判断的是队头位置和城市总数没有准确判断队列是否为空。tt n判断的是队尾位置是否小于城市总数也不是队列是否为空。hh tt队列为空时hh tt条件仍然成立可能继续访问不存在的队列元素。第 35 题选 Dhh tt。五、第 36 题③ 如何更新到达城市的距离选项A.d[y] 1B.d[x] 1C.d[x]D.d[x] - 1正确答案B。1. 题目中的代码if (d[y] -1) { d[y] ③; c[y] c[x] ^ 1; q[tt] y; }这里x是当前正在处理的城市y是从x通过一条道路到达的城市d[x]是起点到x的最少道路数d[y]是起点到y的最少道路数。2. 举个例子假设起点 s → A → B那么d[s] 0 d[A] 1 d[B] 2如果现在正在处理 A并通过一条道路到达 B那么d[B] d[A] 1因为从 A 再走一条道路路程就增加 1。所以d[y] d[x] 1;3. 为什么不是d[y] 1因为d[y]是我们正在准备计算的距离第一次访问它时它还没有被赋值。程序把d[i] -1;作为“还没有访问过”的标记。因此应该根据已经知道距离的当前城市x来计算d[y] d[x] 1;第 36 题选 B。记忆口诀从当前城市再走一步新城市的距离就是当前距离加 1。六、第 37 题④ 如何判断图不是二分图选项A.c[y] c[x]B.w[i] 1C.c[y] ! c[x]D.d[y] 1 ! d[x]正确答案A。这是本题的一个重要考点二分图染色。1. 什么是二分图我们尝试给每个城市涂上两种颜色红色0蓝色1要求每一条道路连接的两个城市颜色必须不同。例如红色城市 —— 蓝色城市 —— 红色城市这符合二分图的染色要求。但如果出现红色城市 —— 蓝色城市 | | └─────────────┘如果道路形成奇数长度的环就可能无法让相邻城市始终颜色不同。2. 程序怎样给城市染色代码c[y] c[x] ^ 1;这里^是按位异或运算。对于 0 和 10 ^ 1 1 1 ^ 1 0所以它的作用就是如果 x 是红色y 就涂蓝色 如果 x 是蓝色y 就涂红色。3. 如果 y 之前已经访问过呢程序会检查if (d[y] -1) { ... } else if (④) ok 0;如果y已经访问过就不能再随意改变它的颜色。因为相邻城市必须颜色不同所以如果发现c[y] c[x]就说明这条道路连接了两个同色城市二分图染色发生冲突。于是ok 0;表示图不满足二分图染色条件。因此第 37 题选 Ac[y] c[x]。七、第 38 题⑤ 最终应该输出 0 还是 1选项A.ok c[s] c[t]B.ok c[s] ! c[t]C.!ok || c[s] c[t]D.!ok c[s] ! c[t]正确答案C。这是整道题最需要综合理解的地方。前面程序已经完成了BFS 搜索判断起点能否到达终点判断道路是否同时存在和-检查图是否为二分图给城市进行 0/1 染色。接下来要根据这些信息决定答案。1. 先看前面的特殊情况程序中有if (d[t] -1) { std::cout -1; return 0; }如果d[t] -1说明 BFS 没有访问到终点t。也就是说根本不存在从s到t的路线。所以输出-1这是题目规定的结果。2. 如果所有道路都是同一种符号呢程序还会判断if (!p || !ng) { std::cout d[t]; return 0; }其中p用来记录是否发现过正权道路ng用来记录是否发现过负权道路。如果!p || !ng成立就说明至少有一种符号的道路不存在。例如所有道路都是。那么一条经过 4 条道路的路线权值就是∣4−0∣4如果所有道路都是-经过 4 条道路的路线权值同样是∣0−4∣4这时权值等于经过的道路数。BFS 求出的d[t]就是最少道路数因此直接输出它。3. 如果正负道路都存在呢当正负道路都存在时程序继续判断if (⑤) std::cout 0; else std::cout 1;我们需要理解为什么答案只需要在 0 和 1 之间选择。因为每走一条道路路线的正负数量差会增加或减少 1。对于一条确定长度的路线 路线长度同时与路线长度具有相同的奇偶性。因此如果能够构造偶数长度的路线就有机会让正负数量完全相等权值为 0如果路线长度必须是奇数正负数量不可能相等最小的绝对差至少为 1。图的二分图染色可以帮助判断路线长度的奇偶性在二分图中同色城市之间的路线长度为偶数异色城市之间的路线长度为奇数。如果图不是二分图存在奇环就可以利用重复走动改变路线长度的奇偶性。所以程序最后的判断条件是!ok || c[s] c[t]意思是!ok图不是二分图c[s] c[t]起点和终点颜色相同。只要其中一个条件成立程序就输出 0否则输出 1。因此第 38 题选 C!ok || c[s] c[t]。八、完整答案与知识点回顾1. 答案汇总题号填空正确选项核心原因34①C转为 1-转为 -135②Dhh tt表示队列不为空36③B新城市距离等于当前距离加 137④A相邻城市同色二分图染色冲突38⑤C判断是否能得到权值 02. 同学们需要掌握的知识这道题把多个知识点串在了一起图的存储使用链式前向星保存道路BFS使用队列逐层访问城市距离数组d[y] d[x] 1二分图染色相邻城市颜色必须不同异或运算c[x] ^ 1可以把 0 和 1 互相切换奇偶性路线长度的奇偶性会影响正负道路数量能否相等。最后送给同学们一句话BFS 帮我们探索城市染色帮我们判断路线的奇偶性而正负道路的数量决定路线是否平衡。这就是“平衡路线”这道题的完整思路。