CSP-S 提高级 · CSP 2026 提高级第一轮 第 19 题

【完善程序1 （平衡路线）】

给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 '+' 或 '-'。对于一条从顶点 s 到顶点 t 的路线，允许重复经过顶点和边，定义一条路线的权值为 |n_+ - n_-|（n_+、n_- 分别为经过的 '+' 边数和 '-' 边数）。请计算从 s 到 t 的路线的最小权值；若不存在则从 s 到 t 的路线，则输出 -1。输入第一行为四个整数 n, m, s, t。接下来 m 行，每行给出两个整数 a, b 和一个字符 '+' 或 '-'，描述一条连接 a 与 b 的无向边及其符号。数据满足 2 ≤ n ≤ 2×10^5，1 ≤ m ≤ 4×10^5，1 ≤ s, t ≤ n 且 s ≠ t，1 ≤ a, b ≤ n，可能出现重边。以下程序通过 BFS 求出最小权值。请补全程序。

#include <iostream>

constexpr int N = 200005;
constexpr int M = 400005;

int n, m, s, t;
int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;
int q[N], d[N], c[N];

void add(int a, int b, int z) {
    e[idx] = b;
    w[idx] = z;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main() {
    std::cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++)
        h[i] = d[i] = c[i] = -1;
    for (int i = 0; i < m; i++) {
        int a, b;
        char op[2];
        std::cin >> a >> b >> op;
        int z = 【①】;
        add(a, b, 

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

BFS 求无权图最短路，同时用 c[] 做二分图染色。① 把 '+'/'-' 变成权值 ±1；② 队列用 hh/tt 双指针，循环条件是 hh < tt；③ 距离由父结点加一；④ 相邻点同色说明出现奇环（非二分图）；⑤ 结论：若全是一条符号（!p 或 !ng）输出距离，否则若存在奇环或 s、t 同色就能凑到 0，否则最小值为 1。

② 误选 hh <= tt（把空槽也出队一次）；⑤ 把 !ok 与 c[s]==c[t] 的连接符号写成 &&，或者把结论方向写反。本题的数学结论（同色→可达 0、异色→最小 1、有奇环→0）需要想清楚再选。

程序分析

问题模型：无向图每条边带符号 '+' 或 '−'，一条 s→t 路线（可重复经过顶点和边）的权值为 |n₊ − n₋|（n₊、n₋ 分别是经过的 '+' 边数和 '−' 边数）。求最小权值，无路则输出 −1。

int z = ① ;                       // 把符号变成权值
...
int hh = 0, tt = 0;
int p = 0, ng = 0, ok = 1;        // p: 存在 '+' 边；ng: 存在 '−' 边；ok: 是否二分图
q[tt++] = s;  d[s] = c[s] = 0;
while ( ② ) {
    int x = q[hh++];
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (w[i] > 0) p = 1;
        if (w[i] < 0) ng = 1;
        if (d[y] == -1) { d[y] = ③ ; c[y] = c[x] ^ 1; q[tt++] = y; }
        else if ( ④ ) ok = 0;
    }
}
if (d[t] == -1) { cout << -1; return 0; }       // s 到不了 t
if (!p || !ng) { cout << d[t]; return 0; }      // 全程只有一种符号
if ( ⑤ ) cout << 0; else cout << 1;

算法主线（这道题的思想含量很高）

1. BFS 分层：d[y] = s 到 y 的最短边数；c[y] = 从 s 出发奇偶染色（c[y] = c[x] ^ 1）。若某个已访问的相邻点与当前点同色，说明存在奇环，图不是二分图 → ok = 0。 2. 只有一种符号时：s→t 的最短路全由同号边组成，此时 |n₊ − n₋| = d[t] 是最小值（也不可能更小，因为每走一条边最多改变 1）。 3. 两种符号都存在时： - 若图不是二分图（有奇环），可以绕着奇环多走一圈把 n₊ − n₋ 的奇偶性翻转，再配合正负边调节，最小值为 0； - 若图是二分图，则对任意 s→t 路线都有 n₊ + n₋ ≡ d[s→t] ≡ c[s] ⊕ c[t] (mod 2)，且 n₊ − n₋ ≡ n₊ + n₋ (mod 2)，所以 n₊ − n₋ 的奇偶性被固定：c[s] = c[t] 时为偶数 → 可以调到 0；c[s] ≠ c[t] 时为奇数 → 最小只能到 1。

逐空分析

① 应填 op[0] == '+' ? 1 : -1 → C 把符号转成权值：'+' 记 +1、'−' 记 −1，这样"边权"就同时承担了"符号"与"计数"两重角色（后续 w[i] > 0 / w[i] < 0 正是用它判断符号种类）。 A 把 '+' 记成 0、'−' 记成 1，符号与计数分离；B 只给出布尔值，无法参与运算与符号判断；D 的映射方向反了。

② 应填 hh < tt → D 手写队列用两个下标：q[tt++] = s 让 tt 指向"下一个空位"，元素区间是 [hh, tt)。循环条件必须是 hh < tt（队列非空）。 C 的 hh <= tt 会多出队一次空槽（q[tt] 是未写入的位置）；A、B 用 n 作上界，与队列的真实长度无关。

③ 应填 d[x] + 1 → B BFS 的层数递推：本点是 x 的邻居，且第一次被访问 → d[y] = d[x] + 1。 A 是 d[y] + 1（y 此时还是 −1，无意义）；C 直接赋 d[x]（层数不增）；D 减一，方向反了。

④ 应填 c[y] == c[x] → A 相邻两点同色 ⟺ 出现了奇环 ⟺ 图不是二分图，此时把 ok 置 0。 B 的 w[i] == 1 只是在看边是不是 '+' 边；C 的 c[y] != c[x] 是"正常染色"（恰恰应该继续），方向反了；D 与染色无关。

⑤ 应填 !ok || c[s] == c[t] → C 由上面的分析：

• !ok（存在奇环，可翻转奇偶性）→ 能凑到 0；
• 或者图是二分图但 c[s] == c[t]（差值为偶数）→ 也能凑到 0；
• 其余情形（二分图且 c[s] ≠ c[t]）→ 最小为 1。

所以输出 0 的条件是 !ok || c[s] == c[t]。 A 用 && 连接，条件过于苛刻（漏掉"有奇环"这一支）；B 和 D 都把 c 的比较方向写反。

本题小结

套路提示：带符号边的"平衡路线"问题本质是奇偶性（二分图染色）分析——先想清"每走一条边差值 ±1、绕圈能改变奇偶性"，再选代码条件。另外，手写队列的 hh < tt 与"链式前向星"（h/e/ne/w）是 CSP 的常客，看到 ne[i] 就要条件反射地想到"遍历 x 的所有邻边"。