CSP-S 2026 第一轮 第 38 题：平衡路线：⑤处应填

题目

给定一张有 $n$ 个顶点、$m$ 条边的无向图，每条边带有符号 '+' 或 '-'。对于一条从顶点 $s$ 到顶点 $t$ 的路线，允许重复经过顶点和边。定义一条路线的权值如下：记 $n^{+}, n^{-}$ 分别为经过的 '+' 边数和经过的 '-' 边数，则该路线的权值为 $∣n^{+}- n^{-}∣$。

请计算从 $s$ 到 $t$ 的路线的最小权值。若不存在从 $s$ 到 $t$ 的路线，则输出 −1。

输入第一行为四个整数 $n, m, s, t$。接下来 $m$ 行，每行给出两个整数 $a, b$ 和一个字符 '+' 或 '-'，描述一条连接 $a$ 与 $b$ 的无向边及其符号。

数据满足 $2 \le n \le 2 \times 10^{5}$，$1 \le m \le 4 \times 10^{5}$，$1 \le s, t \le n$ 且 $s ≠=t$，$1 \le a, b \le 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, z);
        add(b, a, z);
    }
    int hh = 0, tt = 0;
    int p = 0, ng = 0, ok = 1;
    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) {
        std::cout << -1;
        return 0;
    }
    if (!p || !ng) {
        std::cout << d[t];
        return 0;
    }
    if (/* ⑤ */) std::cout << 0;
    else std::cout << 1;
    return 0;
}

⑤处应填（ ）。

选项

• 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

题解

选 C：!ok || c[s] == c[t]。

c[x] 表示 BFS 给顶点染的颜色，相邻顶点应当颜色不同；ok 表示从 \(s\) 出发所在的连通分量是否为二分图。

程序执行到⑤时，已经确定 \(s,t\) 连通，而且这个连通分量中同时存在 '+' 和 '-' 边。

关键有两点：

1. 权值与路线长度的奇偶性相同。

因为 \[ n^+-n^-=(n^++n^-)-2n^-, \] 所以偶数长度的路线才可能得到权值 \(0\)。

1. 两种符号都存在时，可以把差值调整到 \(0\) 或 \(\pm1\)。

在连通分量中，一定能找到一个同时连接正边和负边的顶点。让路线经过它，再沿正边往返一次，差值增加 \(2\)；沿负边往返一次，差值减少 \(2\)。因此，偶数长度路线可以调整到权值 \(0\)，奇数长度路线可以调整到权值 \(1\)。

于是只需判断：是否存在从 \(s\) 到 \(t\) 的偶数长度路线？

• 若 ok == 1，图是二分图，只有 c[s] == c[t] 时存在偶数长度路线。
• 若 ok == 0，图中存在奇环。路线可以绕行奇环来改变长度的奇偶性，所以一定能构造偶数长度路线。

因此应填：

``cpp !ok || c[s] == c[t] ``