AcWing 341. 最优贸易（双向最短路详解）

「爱情、让人受尽委屈。」 2023-02-18 09:48 1阅读 0赞

**题目描述**

C国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到C国旅游。当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。设C国 n 个城市的标号从 1~n，阿龙决定从1号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。因为阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

**输入格式**

第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。

接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。

如果z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。

**输出格式**

一个整数，表示答案。

**数据范围**

1≤n≤100000,  
1≤m≤500000,  
1≤各城市水晶球价格≤100

**输入样例**

5 5
    4 3 5 6 1
    1 2 1
    1 4 1
    2 3 2
    3 5 1
    4 5 2

**输出样例**

**解题思路**

首先本题题意为：**从节点1出发到一个价格最低的节点购买水晶球，再去一个价格最高的节点卖出水晶球，前提是买卖两个节点使可以到达的**。因此可以考虑动态规划的思路，我们假设买卖由节点k分隔，即在节点1-k购买，在节点k-n卖出，当然也可以不买不卖，那么有：

*  从 1 走到 i 的过程中，买入水晶球的最低价格 dmin\[i\]；
 *  从 i 走到 n 的过程中，卖出水晶球的最高价格 dmax\[i\]；

那么显然最大差值为**max(dmax\[i\] - dmin\[i\])**，接下来考虑算法实现。求dmax\[i\] 和dmin\[i\]的过程显然使用最短路算法，由于这次求的最值是节点的权值最值，数值不累计，因此不能使用Dijkstra算法，于是采用spfa求最值，朴素的实现应该是先求节点1到各个节点最小值，然后分别求节点i到节点n的最大值，**这样就等于执行了n次spfa，这样复杂度显然太高，于是考虑反向建图，即将图路径取反，然后求节点n到各个节点的最大距离，这样节点n到节点i的最大距离，就等于原图中节点i到节点n的最大距离，这样只需要执行两次spfa**，节省了很多时间，可参考下边代码实现，代码参考yxc。

**代码**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int N = 100010, M = 2000010;
    
    int n, m;
    int price[N];
    int h[N], rh[N], e[M], ne[M], idx;
    int dmin[N], dmax[N];
    bool st[N];
    
    void add(int *h, int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    //寻找最小距离，flag来区分正反搜索
    void spfa(int *d, int start, int *h, bool flag)
    {
        queue<int> q;
        memset(st, 0, sizeof st);
    
        if (flag) memset(d, 0x3f, sizeof dmin);
    
        q.push(start);
        st[start] = true;
        d[start] = price[start];
    
        while (q.size())
        {
            int t = q.front();
            q.pop();
            st[t] = false;
    
            for (int i = h[t]; ~i; i = ne[i])
            {
                int j = e[i];
                //正搜求最小值，反搜求最大值
                if (flag && d[j] > min(d[t], price[j]) || !flag && d[j] < max(d[t], price[j]))
                {
                    if (flag) d[j] = min(d[t], price[j]);
                    else d[j] = max(d[t], price[j]);
    
                    if (!st[j])
                    {
                        st[j] = true;
                        q.push(j);
                    }
                }
            }
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
    
        memset(h, -1, sizeof h);
        memset(rh, -1, sizeof rh);
    
        for (int i = 1; i <= n; i ++ ) scanf("%d", &price[i]);
        while (m -- )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            //add(rh, b, a)等是反向建图
            add(h, a, b), add(rh, b, a);
            if (c == 2) add(h, b, a), add(rh, a, b);
        }
        
        //分别进行一次spfa
        spfa(dmin, 1, h, true);
        spfa(dmax, n, rh, false);
    
        //枚举求最大差值
        int res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);
    
        printf("%d\n", res);
    
        return 0;
    }