CSP-J 2026 初赛试题解析（第三部分：完善程序题（第一题））精讲

同学们，今天我们要去一个神奇的图论王国探险！

这个王国里有许多城市，城市之间有道路连接。每条道路都带着一个特殊的符号：

• + 道路：走过它，权值增加 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];

我们用小学生容易理解的方式来认识它们。

其中，d[] 和 c[] 是理解后面几个空的关键。

三、第 34 题：① 应该填什么？

选项：

• A. op[0] == '+' ? 0 : 1

• B. op[0] == '+'

• C. op[0] == '+' ? 1 : -1

• D. 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
– → -1

C++ 中的三目运算符可以这样写：

op[0] == '+' ? 1 : -1

它的意思是：

如果 op[0] 是 '+'
z = 1
否则
z = -1

所以：

int z = (op[0] == '+' ? 1 : -1);

第 34 题选 C。

记忆口诀

正号变 1，负号变 -1，路线权值就能用加法计算啦！

四、第 35 题：② BFS 的循环条件是什么？

选项：

• A. hh < n

• B. tt < n

• C. hh <= tt

• D. 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 题选 D：hh < tt。

五、第 36 题：③ 如何更新到达城市的距离？

选项：

• A. d[y] + 1

• B. d[x] + 1

• C. 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] == 1

• C. c[y] != c[x]

• D. d[y] + 1 != d[x]

正确答案：A。

这是本题的一个重要考点：二分图染色。

1. 什么是二分图？

我们尝试给每个城市涂上两种颜色：

• 红色：0

• 蓝色：1

要求：

每一条道路连接的两个城市，颜色必须不同。

例如：

红色城市 —— 蓝色城市 —— 红色城市

这符合二分图的染色要求。

但如果出现：

红色城市 —— 蓝色城市
| |
└─────────────┘

如果道路形成奇数长度的环，就可能无法让相邻城市始终颜色不同。

2. 程序怎样给城市染色？

代码：

c[y] = c[x] ^ 1;

这里 ^ 是按位异或运算。

对于 0 和 1：

0 ^ 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 题选 A：c[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。

这是整道题最需要综合理解的地方。

前面程序已经完成了：

接下来要根据这些信息决定答案。

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. 答案汇总

2. 同学们需要掌握的知识

这道题把多个知识点串在了一起：

• 图的存储：使用链式前向星保存道路；

• BFS：使用队列逐层访问城市；

• 距离数组：d[y] = d[x] + 1；

• 二分图染色：相邻城市颜色必须不同；

• 异或运算：c[x] ^ 1 可以把 0 和 1 互相切换；

• 奇偶性：路线长度的奇偶性会影响正负道路数量能否相等。

最后送给同学们一句话：

BFS 帮我们探索城市，染色帮我们判断路线的奇偶性，而正负道路的数量决定路线是否平衡。

这就是“平衡路线”这道题的完整思路。