「COCI 2022/2023 Contest #3」Baltazar 题解

题目大意

给定一个 $n$ 个节点 $m$ 条边的无向连通图，每条边有正权值。Baltazar 可以从城市 $1$ 到城市 $n$，GPS 会引导他走最短路径。他可以在任意一条边上倒魔法药水，使该边长度增加 $2$。问有多少条边，在倒药水后，$1$ 到 $n$ 的最短路径长度恰好增加 $1$。

解题思路

关键观察

1. 最短路结构：首先需要求出原图中 $1$ 到 $n$ 的最短路径
2. 边分类：将边分为在最短路径上的边和不在最短路径上的边
3. 影响分析：
   • 对于最短路径上的边：增加 $2$ 会使最短路直接增加 $2$
   • 对于非最短路径上的边：增加 $2$ 可能使某条次短路径变成新的最短路

算法核心

阶段一：计算最短路

使用 Dijkstra 算法 计算从节点 $1$ 到所有节点的最短距离 $dis[i]$。

阶段二：标记关键路径

从节点 $n$ 开始反向 DFS，重建一条从 $n$ 到 $1$ 的最短路径，并标记：

• $v[x]$：节点 $x$ 在最短路径上的位置（排名）
• $V[e]$：边 $e$ 是否在最短路径上
• $ed[i]$：最短路径上第 $i$ 条边的编号

阶段三：分析候选边

对于最短路径上的每条边 $e_i$（连接 $s_i$ 和 $s_{i+1}$）：

1. 向前搜索：从 $s_i$ 出发，沿着非最短路径边扩展，记录能到达的最远路径位置 $mx$
2. 向后搜索：从 $s_i$ 出发，寻找能绕到 $s_i$ 之前的替代路径，记录最大距离 $Mx$
3. 判断条件：如果存在绕过当前边的替代路径，且该路径长度合适，则当前边是候选边

代码解析

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 3e5 + 5;
const ll llf = 1e18;

int n, m, h[N], to[M], nxt[M], w[M], cnt = 1;
ll dis[N];
bool vis[N], Vis[N], V[N], ckd[N];
int v[N], s[N], ed[N], tp, Tp;

// Dijkstra 求最短路
void dijk() {
    priority_queue<pair<ll, int>> q;
    q.push({0, 1});
    fill(dis + 1, dis + n + 1, llf);
    dis[1] = 0;
    
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = true;
        
        for (int i = h[x], y; i; i = nxt[i]) {
            y = to[i];
            if (dis[x] + w[i] < dis[y]) {
                dis[y] = dis[x] + w[i];
                q.push({-dis[y], y});
            }
        }
    }
}

// 反向 DFS 标记最短路径
bool dfs(int x) {
    if (x == 1) return s[++Tp] = x, v[x] = Tp, true;
    
    for (int i = h[x], y; i; i = nxt[i]) {
        y = to[i];
        if (dis[y] + w[i] == dis[x]) {
            if (dfs(y)) {
                s[++Tp] = x;
                ed[Tp] = i / 2;  // 记录边编号
                v[x] = V[i / 2] = Tp;
                return true;
            }
        }
    }
    return false;
}

// 向前搜索扩展
void insert(int x, int &mx, int &Mx) {
    vis[x] = true;
    mx = max(mx, v[x]);  // 更新能到达的最远位置
    
    for (int i = h[x], y; i; i = nxt[i]) {
        y = to[i];
        // 沿着最短路扩展
        if (dis[x] + w[i] == dis[y] && !V[i / 2] && !vis[y])
            insert(y, mx, Mx);
        // 记录替代路径信息
        else if (dis[x] + w[i] == dis[y] + 1 && Vis[y])
            Mx = max(Mx, dis[y]);
    }
}

// 向后搜索标记
void bfs(int x) {
    Vis[x] = true;
    for (int i = h[x], y; i; i = nxt[i]) {
        y = to[i];
        if (dis[y] + w[i] == dis[x] && !Vis[y])
            bfs(y);
    }
}

void suball() {
    // 初始化
    fill(vis + 1, vis + n + 1, false);
    fill(Vis + 1, Vis + n + 1, false);
    fill(V + 1, V + m + 1, false);
    fill(ckd + 1, ckd + m + 1, false);
    Tp = tp = 0;
    
    // 标记最短路径
    dfs(n);
    // 标记从 n 可达的节点
    bfs(n);
    
    int mx = 0, Mx = 0;
    fill(vis + 1, vis + n + 1, false);
    
    // 检查最短路径上的每条边
    for (int i = 1; i <= Tp; i++) {
        if (i != 1) {  // 跳过起点
            // 关键判断条件
            if (mx < i && Mx >= dis[s[i]])
                tp++, ckd[ed[i]] = true;
        }
        // 从当前节点开始扩展搜索
        insert(s[i], mx, Mx);
    }
    
    // 输出结果
    cout << tp << '\n';
    for (int i = 1; i <= m; i++)
        if (ckd[i]) cout << i << ' ';
    cout << '\n';
}

算法正确性

判断条件解释

对于最短路径上的边 $e_i$（位置 $i$），它是候选边当且仅当：

1. $mx < i$：从 $s_i$ 向前无法绕过当前边
2. $Mx \geq dis[s_i]$：存在从 $s_i$ 向后绕的替代路径

此时，将 $e_i$ 增加 $2$ 后：

• 原最短路长度变为 $dis[n] + 2$
• 替代路径长度可能为 $dis[n] + 1$
• 因此新的最短路长度为 $dis[n] + 1$

复杂度分析

• 时间复杂度：$O((n + m) \log n)$
  • Dijkstra: $O((n + m) \log n)$
  • DFS/BFS: $O(n + m)$
• 空间复杂度：$O(n + m)$

总结

本题的巧妙之处在于：

1. 逆向思维：从 $n$ 开始反向标记最短路径
2. 双向搜索：同时考虑向前扩展和向后绕路的情况
3. 精确判断：通过位置比较确定哪些边修改后会产生恰好 $+1$ 的效果

这种基于最短路结构和位置分析的方法，对于处理边权修改的影响分析具有很好的参考价值。