洛谷P1073题（2009年NOIP提高组）：最优贸易问题解析——SPFA算法的巧妙应用

一、问题背景

最优贸易问题要求在一个有向图中找到一条路径，使得在这条路径上某点买入、后续某点卖出时能获得最大利润。这是典型的图论问题，考察了图的遍历和动态规划思想。

二、算法选择

使用SPFA(Shortest Path Faster Algorithm)算法，它是Bellman-Ford算法的优化版本，适合处理带权有向图的最短路径问题。

三、完整代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, cost;
};

vector<Edge> G[MAXN], rG[MAXN];
int min_price[MAXN], max_price[MAXN];
int price[MAXN];
bool vis[MAXN];

void spfa(int s, vector<Edge> graph[], int dist[], bool is_min) {
    fill(dist, dist + MAXN, is_min ? INF : -INF);
    fill(vis, vis + MAXN, false);
    queue<int> q;
    dist[s] = price[s];
    q.push(s);
    vis[s] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        for (Edge &e : graph[u]) {
            int v = e.to;
            int new_val = is_min ? min(dist[u], price[v]) : max(dist[u], price[v]);
            if ((is_min && new_val < dist[v]) || (!is_min && new_val > dist[v])) {
                dist[v] = new_val;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    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, z});
        rG[y].push_back({x, z});
        if (z == 2) {
            G[y].push_back({x, z});
            rG[x].push_back({y, z});
        }
    }
    
    spfa(1, G, min_price, true);
    spfa(n, rG, max_price, false);
    
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (min_price[i] != INF && max_price[i] != -INF) {
            ans = max(ans, max_price[i] - min_price[i]);
        }
    }
    
    cout << ans << endl;
    return 0;
}

四、关键思路解析

1. 双向图处理：

• 正向图(G)用于从起点1出发计算最小买入价格

• 反向图(rG)用于从终点n出发计算最大卖出价格

2. SPFA变种应用：

• 传统SPFA用于求最短路径，这里改编用于求路径上的最小/最大值

• 第一次SPFA求从起点到各点的最小价格

• 第二次SPFA在反向图中求从终点到各点的最大价格

3. 利润计算：

• 遍历所有节点，计算各点的(max_price - min_price)

• 取所有差值中的最大值即为答案