最优贸易

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2120 字
正反两次松弛求最低买入价与最高卖出价
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1501
// 题意：混合有向无向图，每城有水晶球价格，从 1 城出发到 n 城，途中选一城买入、之后另一城卖出，求一次贸易的最大差价。
// 思路：正向队列松弛求出 1 到各点路径上的最低买入价 low，在反图上松弛求出各点到 n 路径上的最高卖出价 high，答案为 max(high[i]-low[i])。
// 复杂度：O(N+M) 时间 / O(N+M) 空间
// 易错点：反向那次求的是「i 到 n 路径上的最高价」，是在反图上从 n 出发，方向写反会算出无意义的差价。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;
vector<int> g[MAXN];
vector<int> rg[MAXN];
int price[MAXN];
int low[MAXN];
int high[MAXN];
bool inq[MAXN];
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 1; i <= n; i++) cin >> price[i];
    for(int i = 0; i < m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back(y);
        rg[y].push_back(x);
        if(z == 2){
            g[y].push_back(x);
            rg[x].push_back(y);
        }
    }
    for(int i = 1; i <= n; i++) low[i] = INF;
    low[1] = price[1];
    queue<int> q;
    memset(inq, 0, sizeof(inq));
    q.push(1);
    inq[1] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(size_t i = 0; i < g[u].size(); i++){
            int v = g[u][i];
            int nv = min(low[u], price[v]);
            if(nv < low[v]){
                low[v] = nv;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) high[i] = 0;
    high[n] = price[n];
    memset(inq, 0, sizeof(inq));
    q.push(n);
    inq[n] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(size_t i = 0; i < rg[u].size(); i++){
            int v = rg[u][i];
            int nv = max(high[u], price[v]);
            if(nv > high[v]){
                high[v] = nv;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(low[i] < INF && high[i] - low[i] > ans) ans = high[i] - low[i];
    }
    cout << ans << '\n';
    return 0;
}
最优贸易

正文

一本通·提高篇的其它内容
