洛谷P1073_最优贸易

题目描述

link

分析

题目可以概括为：$n$ 个城市、$m$ 条道路（单向或双向），每个城市 $i$ 有水晶球价格 $p_i$。阿龙从城市 $1$ 出发走到城市 $n$（可以重复经过城市），全程最多做一次买卖——先在某城市买入，再在之后经过的另一个城市卖出，赚取差价；如果无利可图就不做交易。要求最大差价。

关键转化：把"买"和"卖"拆成两个独立的最值问题。对每个城市 $k$，只需要知道两个值：

• $dmin[k]$：从 $1$ 号城市到 $k$ 的路径上，能买到的最低价格；
• $dmax[k]$：从 $k$ 到 $n$ 号城市的路径上，能卖出的最高价格。

答案就是 $\underset{1\le k\le n}{max}(dmax[k]-dmin[k])$。

正确性：若最优买卖是在 $u$ 买入、$v$ 卖出（$1$ 可达 $u$，$u$ 可达 $v$，$v$ 可达 $n$），则路径 $u\to v$ 上的任意中间点 $k$ 都满足 $dmin[k]\le p_u$（$1\to u\to k$ 是合法前缀路径）且 $dmax[k]\ge p_v$（$k\to v\to n$ 是合法后缀路径），所以上式 $\ge$ 最优差价；反过来，对任意 $k$，$dmin[k]$ 对应的买入点能到达 $k$，而 $k$ 能到达 $dmax[k]$ 对应的卖出点，两者构成一笔合法买卖，所以上式 $\le$ 最优差价。两边夹逼即得答案。

思路：双向 SPFA / BFS

边权不参与计算，转移只是对点权取 $min/max$，本质是"可达性 + 最值"问题，用 SPFA（或 BFS）即可：

• 正向图 $hl$ 从 $1$ 出发，$dmin[j]=min(dmin[t],p_j)$；
• 反向图 $hr$（把所有边反向）从 $n$ 出发，$dmax[j]=max(dmax[t],p_j)$。

反向建图的目的是把"从 $k$ 能走到 $n$"转化为"从 $n$ 沿反向边能走到 $k$"，这样两遍最短路就能求出所有 $dmin$ 和 $dmax$。

实现细节：

• 单向边 $a\to b$：正向图加 $a\to b$，反向图加 $b\to a$；双向边（$c=2$）两个方向都加。
• 松弛只会让 $dmin$ 单调减小、$dmax$ 单调增大，且都有上下界，因此算法必然收敛。
• 答案初始化为 $0$，对应"不交易"的情况；不可达的城市会让 $dmax[i]-dmin[i]$ 变成很大的负数，不会影响答案。

复杂度：两遍遍历均为 $O(n+m)$ 级别（SPFA 在本题的最值松弛下收敛很快，也能通过本题数据）。

参考代码

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

const int N = 100010, M = 2000010;

int p[N];
int hl[N], hr[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
int st[N];
int n, m;

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

void spfa(int h[], int dist[], int type) {
    queue<int> q;
    if (type == 1) {
        memset(dmin, 0x3f, sizeof dmin);
        dist[1] = p[1];
        q.push(1);
    } else {
        memset(dmax, -0x3f, sizeof dmax);
        dist[n] = p[n];
        q.push(n);
    }

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = 0;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (type == 1 && dist[j] > min(dist[t], p[j]) || type == 2 && dist[j] < max(dist[t], p[j])) {
                if (type == 1) dist[j] = min(dist[t], p[j]);
                else dist[j] = max(dist[t], p[j]);

                if (!st[j]) {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
}

int main() {
    memset(hl, -1, sizeof hl);
    memset(hr, -1, sizeof hr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(hl, a, b);
        add(hr, b, a);
        if (c == 2) {
            add(hl, b, a);
            add(hr, a, b);
        }
    }

    spfa(hl, dmin, 1);
    spfa(hr, dmax, 2);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dmax[i] - dmin[i]);
    }
    cout << res << endl;

    return 0;
}