「Morskie opowieści」题解：奇偶性在路径存在性问题中的应用

题目概述

我们需要验证 $k$ 个海上冒险故事是否可能发生：

• 有 $n$ 个港口，$m$ 条双向航道
• 每个故事：从港口 $s$ 出发，经过恰好 $d$ 次航行到达港口 $t$
• 可以重复经过同一航道，可以来回航行

数据范围：

• $n \leq 5000, m \leq 5000, k \leq 10^6$
• $d \leq 10^9$

关键洞察

1. 奇偶性的重要性

由于航道是双向的，从一个港口出发，经过：

• 偶数次航行：可能回到原点
• 奇数次航行：必然到达不同港口

更精确地说：从 $u$ 到 $v$ 的路径长度奇偶性是固定的。

2. 可达性条件

对于查询 $(s, t, d)$，需要满足：

1. 可达性：$s$ 和 $t$ 在同一个连通分量中
2. 奇偶性匹配：$d$ 的奇偶性必须与最短路径的奇偶性一致
3. 长度足够：$d \geq$ 最短路径长度

算法设计

数据结构

struct Edge {
    int now, nxt;
} e[N << 1];
int head[N], cur;  // 邻接表存储图

int dis[N][2];     // dis[i][0]: 到i的偶数最短路径
                   // dis[i][1]: 到i的奇数最短路径

核心算法：带奇偶性的 BFS

void spfa(int s) {
    // 初始化
    memset(dis, 0x3f, sizeof dis);
    dis[s][0] = 0;  // 起点，0次航行（偶数）
    
    queue<int> q;
    q.push(s);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        
        for (遍历u的所有邻居v) {
            // 从偶数步到奇数步
            if (dis[u][0] + 1 < dis[v][1]) {
                dis[v][1] = dis[u][0] + 1;
                q.push(v);
            }
            // 从奇数步到偶数步  
            if (dis[u][1] + 1 < dis[v][0]) {
                dis[v][0] = dis[u][1] + 1;
                q.push(v);
            }
        }
    }
}

查询处理

对于每个查询 $(s, t, d)$：

ans = (d >= dis[t][d % 2])

代码详解

1. 图构建

while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    add(u, v), add(v, u);  // 无向图
}

2. 查询分组

for (int i = 1; i <= k; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    query[u].push_back((Query){i, v, w});  // 按起点分组
}

3. 批量处理同一出发点的查询

for (int u = 1; u <= n; u++) {
    if (!query[u].empty() && head[u]) {  // 有查询且不是孤立点
        spfa(u);  // 计算从u出发的所有奇偶最短路径
        
        for (Query t : query[u]) {
            ans[t.id] = (t.w >= dis[t.v][t.w & 1]);
        }
    }
}

正确性证明

为什么只需要检查奇偶性？

定理：如果存在一条从 $s$ 到 $t$ 的长度为 $L$ 的路径，那么对于任意 $d \geq L$ 且 $d \equiv L \pmod{2}$，都存在一条长度为 $d$ 的路径。

证明：

• 在找到的最短路径上，可以在任意一条边上来回走动
• 每次来回增加 2 步，不改变奇偶性
• 因此可以构造出所有满足奇偶性要求且长度足够的路径

孤立点处理

if (!query[u].empty() && head[u])

如果起点是孤立点：

• 只能到达自己（$s = t$）
• 路径长度只能是 0（偶数）
• 其他情况均不可达

复杂度分析

• 空间复杂度：$O(n + m + k)$
• 时间复杂度：
  • BFS: $O(n + m)$ 每次
  • 总复杂度: $O(k + \text{不同起点数} \times (n + m))$

优化：通过按起点分组查询，避免重复计算。

样例分析

以题目样例为例：

8 7 4
1-2-3-4  和  5-6-7-8（环）

查询 1：2 3 1

• 最短路径：2→3，长度1（奇数）
• $1 \geq 1$ 且奇偶匹配 → TAK

查询 2：1 4 1

• 最短路径：1→2→3→4，长度3（奇数）
• $1 < 3$ → NIE

查询 3：5 5 8

• 在环上可以绕圈：5→6→7→8→5（4步）
• 绕两圈：8步 → TAK

查询 4：1 8 10

• 1和8在不同连通分量 → NIE

总结

本题的解决方案展示了如何利用奇偶性这一关键性质来简化路径存在性问题：

1. 问题转化：将"是否存在长度为d的路径"转化为"奇偶性匹配+长度足够"
2. 批量处理：通过查询分组避免重复计算
3. 边界处理：特别注意孤立点的情况

这种奇偶BFS的技巧在很多图论问题中都有应用，特别是在需要处理路径长度模意义的场景下。