CCO 2024 Day1 T1「Treasure Hunt」题解

题目大意

佩里船长在 $N$ 个岛屿和 $M$ 条航线构成的图上寻宝。每个岛屿 $i$ 有宝藏价值 $v_i$，每条航线 $(a_i, b_i, c_i)$ 表示双向通行费用为 $c_i$。

对于每个起点岛屿 $x$，佩里可以沿任意路径走到某个岛屿 $y$，获得净收益 $v_y$ 减去路径总费用。要求对每个 $x$ 输出最大净收益。

数据范围：

• $1 \leq N \leq 10^6$，$0 \leq M \leq 10^6$
• $0 \leq v_i, c_i \leq 10^9$

算法思路

关键观察

设 $d(x,y)$ 为从 $x$ 到 $y$ 的最短路径费用，那么从 $x$ 出发到 $y$ 的净收益为：

对于固定的起点 $x$，最大收益为：

问题转化

我们可以将问题重新解释：建立一个"收益传播"模型：

• 初始时，每个节点 $i$ 的收益 $\text{dis}[i] = v_i$（直接取本地宝藏）
• 如果存在边 $(u,v,w)$，那么可以通过 $u$ "传播"收益到 $v$：$\text{dis}[v] = \max(\text{dis}[v], \text{dis}[u] - w)$
• 最终 $\text{dis}[x]$ 就是从 $x$ 出发能获得的最大收益

算法选择

使用改进的 Dijkstra 算法，但有以下关键区别：

1. 使用大根堆而非小根堆（求最大收益而非最小距离）
2. 初始化所有节点入堆（每个节点都可能是收益起点）
3. 松弛条件：$\text{dis}[v] < \text{dis}[u] - w$

代码实现与注释

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

using ll = long long;  // 使用long long防止溢出

const int N = 1e6 + 10;  // 数组大小

// 链式前向星存图
struct Edge {
    int v, w, nxt;  // 目标节点、边权、下一条边索引
} e[N << 1];  // 无向图，开2倍空间
int head[N], tot = 1;  // 头指针数组，边计数器从1开始

// 添加无向边
void add(int u, int v, int w) {
    e[++tot] = {v, w, head[u]};  // 新边插入链表头部
    head[u] = tot;
}

int n, m, a[N];     // 节点数、边数、节点价值
ll dis[N];          // 最大收益数组

// 大根堆：存储(收益, 节点编号)
priority_queue<pair<ll, int>> Q;

int main() {
    // 读入数据
    scanf("%d%d", &n, &m);
    
    // 初始化：每个节点的收益初始化为自身价值
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        dis[i] = a[i];          // 不移动时的收益
        Q.emplace(a[i], i);     // 所有节点入堆
    }
    
    // 建图
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);  // 无向图添加双向边
        add(v, u, w);
    }
    
    // 主算法：收益传播
    while (!Q.empty()) {
        // 取出当前收益最大的节点
        auto [cur_profit, u] = Q.top();
        Q.pop();
        
        // 如果堆中值小于当前值，说明已被更大收益更新，跳过
        if (dis[u] > cur_profit) continue;
        
        // 遍历所有邻边，尝试传播收益
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w;
            
            // 关键更新：如果通过u到v能获得更大收益
            if (dis[v] < dis[u] - w) {
                dis[v] = dis[u] - w;        // 更新v的收益
                Q.emplace(dis[v], v);       // v入堆继续传播
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; ++i) {
        printf("%lld\n", dis[i]);
    }
    
    return 0;
}

算法正确性证明

贪心选择性质

每次从堆中取出收益最大的节点 $u$，此时 $\text{dis}[u]$ 已经是 $u$ 的最终最大收益。因为：

• 如果有更大收益的路径到达 $u$，该路径上的某个节点收益必然大于 $\text{dis}[u]$
• 但大根堆保证我们总是先处理收益更大的节点
• 因此当处理 $u$ 时，$\text{dis}[u]$ 不可能被后续节点更新得更大

松弛操作正确性

对于边 $(u,v,w)$，松弛条件 $\text{dis}[v] < \text{dis}[u] - w$ 的含义是：

如果存在起点 $x$ 到 $u$ 的收益为 $\text{dis}[u]$，那么从 $x$ 到 $v$ 的收益至少为 $\text{dis}[u] - w$（经过 $u$ 再到 $v$）

复杂度分析

• 时间复杂度：$O((N+M)\log N)$
  • 每个节点最多出堆一次
  • 每次出堆遍历所有邻边
  • 堆操作复杂度 $O(\log N)$
• 空间复杂度：$O(N+M)$

样例验证

以题目样例为例：

4 5
6 5 9 2
1 2 0
3 2 3
4 3 6
1 3 5
2 4 2

执行过程：

1. 初始：$\text{dis} = [6, 5, 9, 2]$
2. 处理节点3（收益9）：更新节点2为6，节点4为3
3. 处理节点1（收益6）：无更新
4. 处理节点2（收益6）：更新节点4为4
5. 处理节点4（收益4）：无更新

最终结果：$[6, 6, 9, 4]$，符合样例输出。

总结

本题通过巧妙的"收益传播"模型，将看似复杂的最优路径问题转化为经典的图算法问题。关键在于：

1. 问题转化：将"从x出发到y的最大收益"转化为"收益传播"
2. 算法选择：改进的Dijkstra算法，使用大根堆求最大值
3. 正确性保证：贪心选择性质确保每次扩展的都是当前最优解

该解法在 $N, M \leq 10^6$ 的数据范围内能够高效运行